--- 1/draft-ietf-ipv6-host-load-sharing-00.txt 2006-02-05 00:02:30.000000000 +0100 +++ 2/draft-ietf-ipv6-host-load-sharing-01.txt 2006-02-05 00:02:30.000000000 +0100 @@ -1,135 +1,203 @@ -INTERNET-DRAFT R. Hinden/Nokia -January 4, 2002 +IPv6 Working Group R. Hinden +INTERNET-DRAFT Nokia +January 26, 2004 D. Thaler +Expires July 2004 Microsoft IPv6 Host to Router Load Sharing - - + Status of this Memo This document is an Internet-Draft and is in full conformance with - all provisions of Section 10 of [RFC2026]. +all provisions of Section 10 of 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 as reference - material or to cite them other than as "work in progress." +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." - To view the list Internet-Draft Shadow Directories, see +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 expires on July 4, 2002. +Copyright Notice -Abstract +Copyright (C) The Internet Society (2004). All Rights Reserved. - This document defines a change to IPv6 Neighbor Discovery that IPv6 - hosts can use to load share their outgoing traffic between multiple - default routers. +Draft IPv6 Host to Router Load Sharing January 2004 -1. Introduction +Abstract - 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. +The original IPv6 conceptual sending algorithm does not require +load-sharing among equivalent IPv6 routers, and suggests schemes +which can be problematic in practice. This document updates the +conceptual sending algorithm so that traffic to different +destinations is distributed among routers in an efficient fashion. - IPv6 Neighbor Discovery protocol does not require any specific - procedure for hosts to divide (i.e., load share) outgoing traffic - between these routers. This document defines procedures that IPv6 - hosts can use to load share their outgoing traffic between multiple - default routers. +1. Introduction - 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]. +In the conceptual sending algorithm in [ND] and in the optional +extension in [ROUTERSEL], a next hop 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 is selected the first time traffic is sent to a specific +destination IP address. Subsequent traffic to the same +destination address continues to use the same router unless there +is some reason to change to a different router (e.g., a redirect +message is received, or a router is found to be unreachable). -2. Background +In both the base algorithm and in the optional extension, +sometimes a host has a choice of multiple equivalent routers for a +destination. That is, all other factors are equal and a host must +break a tie via some implementation-specific means. - RFC2461 "Neighbor Discovery for IPv6" [ND] defines in section 6.3.6 - an algorithm for selecting default routers. This algorithm is - invoked during next hop determination 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 selected the - first time traffic is sent to a specific destination. Subsequent - traffic to the same destination would continue to use this router - unless there was some other reason to change to a different router - (e.g., redirect message received, etc.). +It is desirable when there is more than one equivalent router that +hosts distribute their outgoing traffic among these routers. This +shares the load among multiple routers and provides better +performance for the host's traffic. - ND further specifies that when there are multiple reachable default - routers, an implementation may always return the same router (e.g., - the first in the list) or may cycle through the list of reachable - default routers in a round robin manner. It does not require any - specific behavior in the case of multiple default routers. +[ND] does not require any particular behavior in this respect. It +specifies that an implementation may always choose the same router +(e.g., the first in the list) or may cycle through the routers in +a round-robin manner. Both of these suggestions are problematic. - It is desirable when there is more than one default router that the - hosts distribute their outgoing traffic among these routers. This - document changes the ND behavior to require that an implementation - cycle through the list of default routers in a random order. +Clearly, always choosing the same router does not provide load +sharing. Some problems with naive tie-breaking techniques such as +round-robin and random are discussed in [MULTIPATH]. While the +destination cache provides some stability since the determination +is not per-packet, cache evictions or timeouts can still result in +unstable or unpredictable paths over time, lowering the +performance and making it harder to diagnose problems. Round- +robin selection may also result in synchronization issues among +hosts, where in the worst case the load is concentrated on one -3. Load Sharing +Draft IPv6 Host to Router Load Sharing January 2004 - The load sharing algorithm changes the currently specified default - router selection algorithm to cycle through the list of reachable - default routers in random order. This should have the effect of - distributing outgoing traffic for new destinations among the default - routers. Random selection, versus round robin, is used to avoid - synchronization in the hosts selection of a default router. +router at a time. - Bullet 1) in section 6.3.6 "Default Router Selection" [ND] is - replaced with the following: +In the remainder of this document, the key words "MUST", "MUST +NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", +"RECOMMENDED", "MAY", and "OPTIONAL" are to be interpreted as +described in [RFC2119]. - 1) Routers that are reachable or probably reachable (i.e., in any - state other than INCOMPLETE) SHOULD be preferred over routers - whose reachability is unknown or suspect (i.e., in the - INCOMPLETE state, or for which no Neighbor Cache entry exists). - An implementation SHOULD pick routers from the default router - list in random order while making sure it always returns a - reachable or a probably reachable router when one is available. +2. Load Sharing -4. Acknowledgments +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 use a hash-based scheme, such as those described in +[MULTIPATH], which takes the destination IP address into account. - The author of this document would like to thank Erik Nordmark, Brian - Haberman, Steve Deering, Aron Silverton, and Christian Huitema for - their helpful suggestions. +Note that traffic for a given destination address will use the +same router as long as the Destination Cache Entry for the +destination address is not deleted. With a hash-based scheme, +traffic for a given destination address will use the same router +over time even if the Destination Cache Entry is deleted, as long +as the list of equivalent routers remains the same. -5. Security Considerations +3. Acknowledgments - This document requires an node to cycle through a the list of default - routers. There are no known security issues with this change to IPv6 - Neighbor Discovery. +The authors of this document would like to thank Erik Nordmark, +Brian Haberman, Steve Deering, Aron Silverton, and Christian +Huitema for their helpful suggestions. -6. References +4. Security Considerations - [ADD-ARH] Hinden, R., S. Deering, "IP Version 6 Addressing - Architecture", RFC2373, July 1988. +As mentioned in [MULTIPATH], when next-hop selection is +predictable, an application can synthesize traffic that will all +hash the same, making it possible to launch a denial-of-service +attack against the load sharing algorithm, and overload a +particular router. A special case of this 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. - [ICMPv6] Conta, A., S. Deering, "Internet Control Message Protocol - (ICMPv6) for the Internet Protocol Version 6 (IPv6)", - RFC2463, December 1998. +Draft IPv6 Host to Router Load Sharing January 2004 - [IPv6] Deering, S., R. Hinden, "Internet Protocol, Version 6 - (IPv6) Specification", RFC2460, December 1998. +5. Normative References - [ND] Narten, T., E. Nordmark, W. Simpson, "Neighbor Discovery +[ND] Narten, T., Nordmark, E. and W. Simpson, "Neighbor Discovery for IP Version 6 (IPv6)", RFC2461, December 1998. - [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate +[RFC2119] + Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", RFC2119, BCP0014, March 1997. -7. Author's Address +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. Authors' Addresses Robert Hinden Nokia 313 Fairchild Drive Mountain View, CA 94043 - US - Phone: +1 650 625-2004 - Email: hinden@iprg.nokia.com + Email: 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.