rfc2991.txt

RFC 的详细文档！

Network Working Group                                           D. Thaler
Request for Comments: 2991                                      Microsoft
Category: Informational                                          C. Hopps
                                                     NextHop Technologies
                                                            November 2000


      Multipath Issues in Unicast and Multicast Next-Hop Selection

Status of this Memo

   This memo provides information for the Internet community.  It does
   not specify an Internet standard of any kind.  Distribution of this
   memo is unlimited.

Copyright Notice

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

Abstract

   Various routing protocols, including Open Shortest Path First (OSPF)
   and Intermediate System to Intermediate System (ISIS), explicitly
   allow "Equal-Cost Multipath" (ECMP) routing.  Some router
   implementations also allow equal-cost multipath usage with RIP and
   other routing protocols.  The effect of multipath routing on a
   forwarder is that the forwarder potentially has several next-hops for
   any given destination and must use some method to choose which next-
   hop should be used for a given data packet.

1.  Introduction

   Various routing protocols, including OSPF and ISIS, explicitly allow
   "Equal-Cost Multipath" routing.  Some router implementations also
   allow equal-cost multipath usage with RIP and other routing
   protocols.  Using equal-cost multipath means that if multiple equal-
   cost routes to the same destination exist, they can be discovered and
   used to provide load balancing among redundant paths.

   The effect of multipath routing on a forwarder is that the forwarder
   potentially has several next-hops for any given destination and must
   use some method to choose which next-hop should be used for a given
   data packet.  This memo summarizes current practices, problems, and
   solutions.







Thaler & Hopps               Informational                      [Page 1]

RFC 2991                    Multipath Issues               November 2000


2.  Concerns

   Several router implementations allow multipath forwarding.  This is
   sometimes done naively via round-robin, where each packet matching a
   given destination route is forwarded using the subsequent next-hop,
   in a round-robin fashion.  This does provide a form of load
   balancing, but there are several problems with approaches such as
   round-robin or random:

   Variable Path MTU
         Since each of the redundant paths may have a different MTU,
         this means that the overall path MTU can change on a packet-
         by-packet basis, negating the usefulness of path MTU discovery.

   Variable Latencies
         Since each of the redundant paths may have a different latency
         involved, having packets take separate paths can cause packets
         to always arrive out of order, increasing delivery latency and
         buffering requirements.

         Packet reordering causes TCP to believe that loss has taken
         place when packets with higher sequence numbers arrive before
         an earlier one.  When three or more packets are received before
         a "late" packet, TCP enters a mode called "fast-retransmit" [6]
         which consumes extra bandwidth (which could potentially cause
         more loss, decreasing throughput) as it attempts to
         unnecessarily retransmit the delayed packet(s).  Hence,
         reordering can be detrimental to network performance.

   Debugging
         Common debugging utilities such as ping and traceroute are much
         less reliable in the presence of multiple paths and may even
         present completely wrong results.

   In multicast routing, the problem with multiple paths is that
   multicast routing protocols prevent loops and duplicates by
   constructing a single tree to all receivers of the same group
   address.  Multicast routing protocols deployed today (DVMRP, PIM-DM,
   PIM-SM) [2] construct shortest-path trees rooted at either the
   source, or another router known as a Core or Rendezvous Point.
   Hence, the way they ensure that duplicates will not arise is that a
   given tree must use only a single next-hop towards the root of the
   tree.








Thaler & Hopps               Informational                      [Page 2]

RFC 2991                    Multipath Issues               November 2000


3.  Requirements

   In the remainder of this document, we will use the term "flow" to
   represent the granularity at which the router keeps state (if at all)
   for classes of traffic.  The exact definition of a flow may depend on
   the actual implementation.  For example, a flow might be identified
   solely by destination address, or it might be identified by (source
   address, destination address, protocol id) triplet.  Hence "flow" is
   not necessarily synonymous with the term "microflow" as used in RFC
   2474 [7], which also includes port numbers.  Indeed, including
   transport-layer information in the next-hop selection process can
   actually be problematic.  For example, if packets are fragmented, the
   transport-layer information may not be available in every packet.
   Furthermore, having the choice of path depend on transport-layer
   fields may negate the benefit of caching information such as MTU for
   use in subsequent connections between the same endpoints.

   All of the problems outlined in the previous section arise when
   packets in the same unicast or multicast "flow" are split among
   multiple paths.  The natural solution is therefore to ensure that
   packets for the same flow always use the same path.

   Two additional features are desirable:

   Minimal disruption
         When multipath is used, meaning that multiple routes contribute
         valid next-hops, the chances are higher of routes being added
         and deleted from consideration than when only the "best" route
         is used (in which case metric changes in alternate routes have
         no effect on traffic paths).  Since a higher number of routes
         may actually be used for forwarding when multipath is in use,
         the potential for packet reordering and packet loss due to
         route flaps can be much greater than when not using multipath.
         Hence, it is desirable to minimize the number of active flows
         affected by the addition or deletion of another next-hop.

   Fast implementation
         The amount of additional computation required to forward a
         packet should be small.  For example, when doing round-robin,
         this computation might consist of incrementing (modulo the
         number of next-hops) a next-hop index.

4.  Solutions

   We now provide three possible methods for improving the performance
   of multipath and then discuss their applicability to unicast and
   multicast forwarding.




Thaler & Hopps               Informational                      [Page 3]

RFC 2991                    Multipath Issues               November 2000


   Modulo-N Hash
         To select a next-hop from the list of N next-hops, the router
         performs a modulo-N hash over the packet header fields that
         identify a flow.  This has the advantage of being fast, at the
         expense of (N-1)/N of all flows changing paths whenever a
         next-hop is added or removed.

   Hash-Threshold
         The router first selects a key by performing a hash over the
         packet header fields that identify the flow.  The N next-hops
         have been assigned unique regions in the hash function's output
         space.  By comparing the hash value against region boundaries
         the router can determine which region the hash value belongs to
         and thus which next-hop to use.  This method has the advantage
         of only affecting flows near the region boundaries (or
         thresholds) when next-hops are added or removed.  For ECMP
         hash-threshold's lookup can be done with a simple division
         (hash_value / fixed_region_size).  When a next-hop is added or
         removed, between 1/4 and 1/2 of all flows change paths.  An
         analysis of this method can be found in [3].

   Highest Random Weight (HRW)
         The router computes a key for EACH next-hop by performing a
         hash over the packet header fields that identify the flow, as
         well as over the address of the next-hop.  The router then
         chooses the next-hop with the highest resulting key value [4].
         This has the advantage of minimizing the number of flows
         affected by a next-hop addition or deletion (only 1/N of them),
         but is approximately N times as expensive as a modulo-N hash.

   The applicability of these three alternatives depends on (at least)
   two factors: whether the forwarder maintains per-flow state, and how
   precious CPU is to a multipath forwarder.

   Some routers may maintain per-flow state for reasons other than for
   supporting multipath.  For example, routers typically keep per-flow
   state for multicast flows so that they can maintain the list of
   interfaces to which packets in the flow should be copied.

   If per-flow state is maintained in a multipath forwarder, then
   computation of the next-hop can be done by the router at state
   creation time.  This entails no additional computations at packet
   forwarding time compared with normal forwarding to a single next-hop,
   since the next-hop is precomputed.  In this case, any method can be
   used, including round-robin, random, modulo-N, hash-threshold or HRW.
   Hash functions such as modulo-N, hash-threshold and HRW are better if
   the forwarder state may be deleted for any reason during the lifetime
   of a flow since subsequent next-hop computations by the router will



Thaler & Hopps               Informational                      [Page 4]

RFC 2991                    Multipath Issues               November 2000


   always select the same path.  This also improves the usefulness of
   debugging utilities such as traceroute.  Finally, to maximize the
   stability of paths (and hence the usefulness of traceroute, etc.),
   the use of HRW is recommended over the other methods mentioned
   herein.

   If per-flow state is not maintained by the forwarder, then using
   multiple next-hops requires that the next-hop be calculated at packet
   arrival time.  When CPU is more precious than stability of flow
   paths, hash-threshold is recommended over the other methods mentioned
   herein.

4.1.  Unicast Forwarding

   Depending on the implementation, unicast forwarding may or may not
   keep per-flow state.  We recommend that where forwarder
   implementations keep flow state, routers should use HRW at state
   creation time (and next-hop deletion time) to select the next-hop,
   and that forwarders without per-flow state use hash-threshold.

4.2.  Multicast Forwarding

   Today's multicast forwarding engines use a cache of forwarding
   entries indexed by group (or group prefix) and source (or source