idnits 2.17.1 draft-thaler-multipath-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Cannot find the required boilerplate sections (Copyright, IPR, etc.) in this document. Expected boilerplate is as follows today (2024-04-26) according to https://trustee.ietf.org/license-info : IETF Trust Legal Provisions of 28-dec-2009, Section 6.a: This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 2: Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 3: This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://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 described in the Simplified BSD License. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity. ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. == Mismatching filename: the document gives the document name as 'draft-ietf-thaler-multipath-00', but the file name used is 'draft-thaler-multipath-00' == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an Abstract section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. Miscellaneous warnings: ---------------------------------------------------------------------------- == Couldn't figure out when the document was first submitted -- there may comments or warnings related to the use of a disclaimer for pre-RFC5378 work that could not be issued because of this. Please check the Legal Provisions document at https://trustee.ietf.org/license-info to determine if you need the pre-RFC5378 disclaimer. -- The document date (13 January 1997) is 9965 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) ** Obsolete normative reference: RFC 2178 (ref. '1') (Obsoleted by RFC 2328) -- Possible downref: Normative reference to a draft: ref. '2' -- Possible downref: Non-RFC (?) normative reference: ref. '3' ** Obsolete normative reference: RFC 2117 (ref. '4') (Obsoleted by RFC 2362) Summary: 11 errors (**), 0 flaws (~~), 3 warnings (==), 3 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Internet Engineering Task Force Dave Thaler 3 INTERNET-DRAFT Merit 4 Expires July 1998 13 January 1997 6 Multipath Issues in Unicast and Multicast 7 9 Status of this Memo 11 This document is an Internet Draft. Internet Drafts are working 12 documents of the Internet Engineering Task Force (IETF), its Areas, and 13 its Working Groups. Note that other groups may also distribute working 14 documents as Internet Drafts. 16 Internet Drafts are valid for a maximum of six months and may be 17 updated, replaced, or obsoleted by other documents at any time. It is 18 inappropriate to use Internet Drafts as reference material or to cite 19 them other than as a "work in progress". 21 1. Introduction 23 Various routing protocols, including OSPF [1] and ISIS, allow ''Equal- 24 Cost Multipath'' routing. At least two vendors also allow equal-cost 25 multipath usage with RIP [2]. Using equal-cost multipath means that if 26 multiple equal-cost routes to the same destination exist, they can all 27 be discovered and used to provide load balancing among redundant paths. 29 The effects of multipath routing on a forwarder is that the forwarder 30 potentially has several next-hops for any given destination and must use 31 some method to choose which next-hop should be used for a given data 32 packet. In this memo, we describe current practice, problems with 33 this, and potential solutions. 35 Draft Multipath January 1997 37 2. Concerns 39 At least two deployed router implementations allow multipath forwarding. 40 This is typically done via round-robin, where each packet matching a 41 given destination route is forwarded using the subsequent next-hop in a 42 round-robin fashion. This approach does provide a form of load 43 balancing, but there are several problems with this approach: 45 Variable Path MTU 46 Since each of the redundant paths may have a different MTU, this 47 means that the overall path MTU can change on a packet-by-packet 48 basis, negating the usefulness of path MTU discovery. 50 Variable Bandwidth 51 Since each of the redundant paths may have a different bandwidth 52 available, this may also change on a packet-by-packet basis. 53 Rate-adaptive protocols such as TCP are designed to optimize their 54 performance to adapt to the available bandwidth. Varying this on a 55 packet-by-packet basis causes problems with TCP's congestion 56 control mechanisms, resulting in much lower throughputs. 58 Variable Latencies 59 Since each of the redundant paths may have a different latency 60 involved, having packets take separate paths can cause packets to 61 always arrive out of order, increasing delivery latency and 62 buffering requirements. 64 Debugging 65 Common debugging utilities such as ping and traceroute are much 66 less reliable in the presence of multiple paths and may even 67 present completely wrong results. 69 In multicast routing, the problem with multiple paths is that loops and 70 duplicates are prevented by constructing a single tree to all receivers 71 of the same group address. Multicast routing protocols available today 72 construct use shortest-path trees rooted at some point (either the 73 source address, or the address of another router known as a Core or 74 Rendezvous Point) [2]. Hence, the way they insure that duplicates will 75 not arise is that a given tree must use only a single next-hop towards 76 the root of the tree. 78 Draft Multipath January 1997 80 3. Requirements 82 All of the problems outlined in the previous section arise when packets 83 in the same (unicast or multicast) session are split among multiple 84 paths. The natural solution is therefore to insure that packets for the 85 same session (or flow) always use the same path. 87 Two additional features are desirable: 89 Minimal disruption 90 When multipath is used, meaning that multiple routes contribute 91 valid next-hops, the chances are higher of routes being added and 92 deleted from consideration than when only the "best" route is used 93 (in which case metric changes in alternate routes have no effect on 94 traffic paths). Hence, it is desirable to minimize the number of 95 sessions affected by the addition or deletion of another path. 97 Fast implementation 98 The amount of additional computation required to forward a packet 99 must be as small as possible. For example, when doing round-robin, 100 this computation might consist of incrementing (modulo the number 101 of next-hops) a next-hop index. 103 4. Solutions 105 We now provide two possible methods for improving the performance of 106 multipath and then discuss their applicability to unicast and multicast 107 forwarding. 109 Modulo-N Hash 110 To select a next-hop from the list of N next-hops, the router 111 performs a modulo-N hash over the IP header fields that identify a 112 session. This has the advantage of being fast, at the expense of 113 (N-1)/N of all sessions changing paths whenever a next-hop is added 114 or removed. 116 Highest Random Weight (HRW) 117 The router uses a simple pseudo-random number function seeded with 118 the IP header fields that identify a session, as well as a next-hop 119 identifier (address or index) to assign a weight to each of the N 121 Draft Multipath January 1997 123 next hops. An analysis of various deterministic weight functions 124 can be found in [3]. The next-hop receiving the highest weight is 125 chosen as the next hop. This has the advantage of minimizing the 126 number of sessions affected by a next-hop addition or deletion, but 127 is approximately N times as expensive as a modulo-N hash. 129 The applicability of these two alternatives depends on (at least) two 130 factors: whether the forwarder maintains per-flow state (or any finer 131 classification than "all unicast traffic" and "all multicast traffic"), 132 and how precious CPU is to a multipath forwarder. 134 If per-flow state is maintained in a multipath forwarder, then 135 computation of the next-hop can be done by the router at state creation 136 time. This entails no additional computations at packet forwarding time, 137 since the next-hop is precomputed. In this case, any method can be 138 used, including round-robin, random, modulo-N, or HRW. Hash functions 139 such as modulo-N and HRW are better if the forwarder state may be 140 deleted for any reason during the lifetime of a session since subsequent 141 next-hop computations by the router will always select the same path. 142 This also improves the usefulness of debugging utilities such as 143 traceroute. Finally, to maximize the stability of paths (and hence the 144 usefulness of traceroute, etc.), we specifically recommend the use of 145 HRW. 147 If no state finer than "all packets" is maintained in the forwarder, 148 then using multiple next-hops requires that the next-hop be calculated 149 at packet arrival time. When CPU is more precious than stability of 150 session paths, a simple modulo-N hash may be used. 152 4.1. Unicast Forwarding 154 Depending on the implementation, unicast forwarding may or may keep 155 per-flow state. We recommend that where forwarder implementations keep 156 flow state, routers should use HRW at state creation time (and next-hop 157 deletion time) to select next-hop, and that forwarders without per-flow 158 state use a modulo-N hash over the source and destination addresses. 160 4.2. Multicast Forwarding 162 Multicast forwarding uses a cache of forwarding entries indexed by group 163 (or group prefix) and source (or source prefix). This means that, 164 logically, a multicast forwarder always keeps per-"session" state, 165 although a "session" may be fairly coarse (e.g., traffic from all 166 Draft Multipath January 1997 168 sources to the same destination), depending on the multicast routing 169 protocol in use. Since per-session state is kept by the forwarder, it is 170 recommended that the router always use HRW to select the next-hop. 172 Routers using explicit-joining protocols such as PIM-SM [4] should thus 173 use the multipath information when determining to which neighbor a join 174 message should be sent. For example, when multiple next-hops exist for 175 a given Rendezvous Point (RP) toward which a (*,G) Join should be sent, 176 it is recommended that HRW be used to select the next-hop to use for 177 each group. 179 5. References 181 [1] Moy, J., "OSPF Version 2", RFC 2178, July 1997. 183 [2] Semeria, C., and T. Maufer, "Introduction to IP Multicast Routing", 184 draft-ietf-mboned-intro-multicast-03.txt, October 1997. 186 [3] Thaler, D., and C.V. Ravishankar, "Using Name-Based Mappings to 187 Increase Hit Rates", IEEE/ACM Transactions on Networking, February 188 1998. 190 [4] Estrin, D., Farinacci, D., Helmy, A., Thaler, D., Deering, S., 191 Handley, M., Jacobson, V., Liu, C., Sharma, P., and L. Wei, 192 "Protocol Independent Multicast - Sparse Mode (PIM-SM): Protocol 193 Specification", RFC 2117, June 1997. 195 6. Security Considerations 197 Security issues are not discussed in this memo. 199 7. Author's Address 201 Dave Thaler 202 Merit Network, Inc 203 4251 Plymouth Rd., Suite C 204 Ann Arbor, MI 48105-2785 205 Phone: +1 313 647 4813 206 EMail: thalerd@merit.net