INTERNET-DRAFT
IPv6 Working Group                                       R. Hinden/Nokia Hinden
INTERNET-DRAFT                                               Nokia
January 4, 2002 26, 2004                                         D. Thaler
Expires July 2004                                        Microsoft

                 IPv6 Host to Router Load Sharing

               <draft-ietf-ipv6-host-load-sharing-00.txt>
            <draft-ietf-ipv6-host-load-sharing-01.txt>

Status of this Memo

This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of [RFC2026]. RFC2026.

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 Internet-
Drafts as reference material or to cite them other than as "work
in progress."

   To view the

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, see Directories can be accessed at
http://www.ietf.org/shadow.html.

   This internet draft expires on July 4, 2002.

Abstract

   This document defines a change to IPv6 Neighbor Discovery that

Copyright Notice

Copyright (C) The Internet Society (2004).  All Rights Reserved.

Draft            IPv6
   hosts can use Host to load share their outgoing traffic between multiple
   default routers.

1.  Introduction

   IPv6 hosts on a LAN will usually learn about default routers by
   receiving Router Advertisements sent using the IPv6 Neighbor
   Discovery protocol [ND].  If there are multiple routers the hosts
   will automatically learn about them and have multiple default routers
   to send off link traffic. Load Sharing     January 2004

Abstract

The original IPv6 Neighbor Discovery protocol conceptual sending algorithm does not require any specific
   procedure for hosts to divide (i.e., load share) outgoing traffic
   between these routers.  This document defines procedures that
load-sharing among equivalent IPv6
   hosts can use to load share their outgoing traffic between multiple
   default routers.

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", routers, and "OPTIONAL" suggests schemes
which can be problematic in this practice.  This document are updates the
conceptual sending algorithm so that traffic to be interpreted as described in [RFC 2119].

2. Background

   RFC2461 "Neighbor Discovery for IPv6" [ND] defines different
destinations is distributed among routers in section 6.3.6 an efficient fashion.

1.  Introduction

In the conceptual sending algorithm for selecting default routers.  This algorithm is
   invoked during in [ND] and in the optional
extension in [ROUTERSEL], a next hop determination is chosen when no destination
cache entry exists for an off-link destination or when
communication through an existing router is failing.  Normally a
router would be is selected the first time traffic is sent to a specific destination.
destination IP address.  Subsequent traffic to the same
destination would continue address continues to use this the same router unless there was
is some other reason to change to a different router (e.g., a redirect
message is received, etc.).

   ND further specifies that when there are multiple reachable default
   routers, an implementation may always return the same or a router (e.g., is found to be unreachable).

In both the first base algorithm and in the list) or may cycle through the list of reachable
   default routers in optional extension,
sometimes a round robin manner.  It does not require any
   specific behavior in the case host has a choice of multiple default routers. equivalent routers for a
destination.  That is, all other factors are equal and a host must
break a tie via some implementation-specific means.

It is desirable when there is more than one default equivalent router that the
hosts distribute their outgoing traffic among these routers.  This
   document changes the ND behavior to require that an implementation
   cycle through
shares the list of default load among multiple routers in a random order.

3. Load Sharing

   The load sharing algorithm changes and provides better
performance for the host's traffic.

[ND] does not require any particular behavior in this respect.  It
specifies that an implementation may always choose the currently specified default same router selection algorithm to
(e.g., the first in the list) or may cycle through the list of reachable
   default routers in
a round-robin manner.  Both of these suggestions are problematic.

Clearly, always choosing the same router does not provide load
sharing.  Some problems with naive tie-breaking techniques such as
round-robin and random order.  This should have are discussed in [MULTIPATH].  While the effect of
   distributing outgoing traffic for new destinations among
destination cache provides some stability since the default
   routers.  Random selection, versus round robin, determination
is used to avoid
   synchronization not per-packet, cache evictions or timeouts can still result in
unstable or unpredictable paths over time, lowering the hosts
performance and making it harder to diagnose problems.  Round-
robin selection of a default router.

   Bullet 1) may also result in section 6.3.6 "Default Router Selection" [ND] synchronization issues among
hosts, where in the worst case the load is
   replaced with concentrated on one

Draft            IPv6 Host to Router Load Sharing     January 2004

router at a time.

In the following:

     1) Routers that remainder of this document, the key words "MUST", "MUST
NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT",
"RECOMMENDED", "MAY", and "OPTIONAL" are reachable or probably reachable (i.e., to be interpreted as
described in any
        state other than INCOMPLETE) [RFC2119].

2.  Load Sharing

When a host chooses from multiple equivalent routers, it MUST
choose using some method which distributes load for different
destinations among the equivalent routers.  That is, a host MUST
NOT always choose the same router (e.g., the first in the list).
A host SHOULD be preferred over routers
        whose reachability is unknown or suspect (i.e., use a hash-based scheme, such as those described in
[MULTIPATH], which takes the
        INCOMPLETE state, or destination IP address into account.

Note that traffic for which no Neighbor Cache entry exists).
        An implementation SHOULD pick routers from a given destination address will use the default
same router
        list in random order while making sure it always returns as long as the Destination Cache Entry for the
destination address is not deleted.  With a
        reachable or hash-based scheme,
traffic for a probably reachable given destination address will use the same router when one
over time even if the Destination Cache Entry is available.

4. deleted, as long
as the list of equivalent routers remains the same.

3.  Acknowledgments

The author authors of this document would like to thank Erik Nordmark,
Brian Haberman, Steve Deering, Aron Silverton, and Christian
Huitema for their helpful suggestions.

5.

4.  Security Considerations

   This document requires

As mentioned in [MULTIPATH], when next-hop selection is
predictable, an node application can synthesize traffic that will all
hash the same, making it possible to cycle through launch a denial-of-service
attack against the list load sharing algorithm, and overload a
particular router.  A special case of default
   routers.  There are no known security issues with this change is when the same
(single) next-hop is always selected, such as in the algorithm
allowed by [ND].  Introducing hashing can make such an attack more
difficult; the more unpredictable the hash is, the harder it
becomes to conduct a denial-of-service attack against any single
router.

Draft            IPv6
   Neighbor Discovery.

6. Host to Router Load Sharing     January 2004

5.  Normative References

   [ADD-ARH] Hinden, R., S. Deering, "IP Version 6 Addressing
             Architecture", RFC2373, July 1988.

   [ICMPv6]  Conta, A., S. Deering, "Internet Control Message Protocol
             (ICMPv6) for the Internet Protocol Version 6 (IPv6)",
             RFC2463, December 1998.

   [IPv6]    Deering, S., R. Hinden, "Internet Protocol, Version 6
             (IPv6) Specification", RFC2460, December 1998.

[ND] Narten, T., E. Nordmark, E. and W. Simpson, "Neighbor Discovery
     for IP Version 6 (IPv6)", RFC2461, RFC 2461, December 1998.

[RFC2119]
     Bradner, S., "Key words for use in RFCs to Indicate
     Requirement Levels", RFC2119, RFC 2119, BCP0014, March 1997.

6.  Informative References

[MULTIPATH]
     Thaler, D. and C. Hopps, "Multipath Issues in Unicast and
     Multicast Next-Hop Selection", RFC 2991, November 2000.

[ROUTERSEL]
     Draves, R. and D. Thaler, "Default Router Preferences and
     More-Specific Routes", Work in progress, draft-ietf-
     ipv6-router-selection-03.txt, December 2003.

7. Author's Address  Authors' Addresses

     Robert Hinden
     Nokia
     313 Fairchild Drive
     Mountain View, CA  94043
   US
     Phone: +1 650 625-2004
     Email: hinden@iprg.nokia.com bob.hinden@nokia.com

     Dave Thaler
     Microsoft Corporation
     One Microsoft Way
     Redmond, WA  98052
     Phone: +1 425 703 8835
     EMail: dthaler@microsoft.com

8.  Revision History

(This section to be removed before publication as an RFC)

Changes from draft-ietf-ipv6-router-selection-02.txt:

Draft            IPv6 Host to Router Load Sharing     January 2004

o    Split load sharing back into its own document.

o    Made hash-based, rather than random, the rule.

9.  Full Copyright Statement

Copyright (C) The Internet Society (2004).  All Rights Reserved.

This document and translations of it may be copied and furnished
to others, and derivative works that comment on or otherwise
explain it or assist in its implmentation may be prepared, copied,
published and distributed, in whole or in part, without
restriction of any kind, provided that the above copyright notice
and this paragraph are included on all such copies and derivative
works.  However, this document itself may not be modified in any
way, such as by removing the copyright notice or references to the
Internet Society or other Internet organizations, except as needed
for the purpose of developing Internet standards in which case the
procedures for copyrights defined in the Internet Standards
process must be followed, or as required to translate it into
languages other than English.

The limited permissions granted above are perpetual and will not
be revoked by the Internet Society or its successors or assigns.

This document and the information contained herein is provided on
an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET
ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.