Subject: suggested added text for multipath in draft-ietf-mpls-lsp-ping-01

From: Curtis Villamizar <[email-masked]>
Date: Mon, 23 Dec 2002 17:37:59 -0500

The long awaited part 3 of 3.  Same format - diffs.  This is not to
say the document is done.  I didn't address all the comments to the
list as I would expect the authors of the document to do that.

Curtis

@@ -352,26 +451,28 @@
       .                                                               .
       |                                                               |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 
    Types are defined below; Length is the length of the Value field in
    octets.  The Value field depends on the Type; it is zero padded to
    align to a four-octet boundary.
 
           Type #                           Value Field
           ------                           -----------
                1                           Target FEC Stack
                2                           Downstream Mapping
-               3                           Pad
-               4                           Error Code
+	       3			   Downstream Multipath Mapping
+	       4			   Multipath Exercise
+           65534                           Pad
+           65535                           Error Code
 
 3.1. Target FEC Stack
 
    A Target FEC Stack is a list of sub-TLVs.  The number of elements is
    determined by the looking at the sub-TLV length fields.
 
       Sub-Type #       Length              Value Field
       ----------       ------              -----------
                1            5              LDP IPv4 prefix
                2           17              LDP IPv6 prefix
                3           20              RSVP IPv4 Session Query
                4           56              RSVP IPv6 Session Query
@@ -622,39 +723,179 @@
    LSR X.  If a packet with outermost label L and TTL n>1 arrived at X
    on interface I, X must be able to compute which LSRs could receive
    the packet with TTL=n+1, and what label they would see.  (It is
    outside the scope of this document to specify how this computation
    may be done.)  The set of these LSRs are the downstream routers (and
    their corresponding labels) for X with respect to L.
 
    The case where X is the LSR originating the echo request is a special
    case.  X needs to figure out what LSRs would receive a labelled
    packet with TTL=1 when X tries to send a packet to the FEC Stack that
    is being pinged.
 
-3.3. Pad TLV
+3.3 Downstream Multipath Mapping
+
+   The Downstream Multipath Mapping is an optional TLV in an echo
+   request.  The Length is 4 octets plus the size of Multipath
+   Exercise TLVs and Downstream Mapping TLVs contained within the
+   Downstream Multipath Mapping TLV.
+
+   The Downstream Multipath Mapping TLV contains one or more pairs of
+   Multipath Exercise TLVs and Downstream Mapping TLVs.  The
+   Downstream Multipath Mapping TLV is used where multiple forwarding
+   paths exist.  Each Multipath Exercise TLV provides information that
+   can be used to determine how to build test packets to exercise a
+   specific next hop.  Each corresponding Downstream Mapping TLV
+   provides the downstream mapping information for that path.
+
+       0                   1                   2                   3
+       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+      |  Number of Multipaths         |  Type of Multipath            |
+      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+      |  Life Type    |  Shelf Life in Milliseconds                   |
+      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+      |  Multipath Exercise TLV                                       |
+      .                                                               .
+      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+      |  Downstream Mapping TLV                                       |
+      .                                                               .
+      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+      ..... more Multipath Exercise / Downstream Mapping TLV pairs ....
+      .                                                               .
+      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+
+   The "Number of Multipaths" gives the number of multipaths and
+    determines the number of Multipath Exercise and Downstream Mapping
+    TLV pairs to follow unless TLV or packet size limits cause
+    truncation.
+
+    The "Type of Multipath" gives the type of multipath split
+    performed at the branchpoint.  The "Type of Multipath" is needed
+    to interpret the Multipath Exercise TLVs.  Supported types are:
+
+        Type of Multipath      Meaning
+        -----------------      -------
+                        1      Per packet split (use of this form of
+                               multipath is highly discouraged).
+                        2      Seeded unspecified hash based on
+                               underlying labels.
+                        3      Seeded unspecified hash based on IP
+                               source and destination.
+                        4      Seeded unspecified hash based on IP
+                               source and destination for stack depth
+                               of one, based on underlying labels for
+                               stack depth greater than one.
+                        5      Other or unspecified.
+
+    The "Shelf Life in Milliseconds" allows the amount of time that
+    the multipath mapping will remain in effect to be specified, with
+    a range of 1 msec to 16,000 seconds to 4.5 hours.  A value of zero
+    indicates the mapping will remain in place at least until a
+    topology change occurs.  The "Life Type" field is a bit map.  The
+    MSB (0x80) indicates that the given life time is expressed as a
+    maximum shelf life and that the remaining shelf life is not know.
+
+    An Echo Request need not include description of all paths and may
+    be reduced in size by including only the path under test.  If
+    packet size limit or TLV size limits (65535 bytes) would prevent
+    the entire set of paths from being listed in an Echo Response TLV,
+    the total number of paths should be listed in the "Number of
+    Multipaths" field and as many pairs of Multipath Exercise TLVs and
+    Downstream Mapping TLV as fit should be included.
+
+3.4 Multipath Exercise
+
+   The Multipath Exercise TLV may appear only within a Downstream
+   Multipath Mapping TLV.  The Multipath Exercise TLV is omitted when
+   "Type of Multipath" is equal to 1.  The path is not deterministic.
+   The path cannot be determined solely by the packet encapsulation.
+
+   The following encapsulation of the Multipath Exercise TLV is
+   applicable to "Type of Multipath" values 2-4.  The size of the
+   Multipath Exercise TLV is 4 octets plus either an addtional 4
+   octets per included "IP Address or Next Label" containing IPv4
+   addresses or MPLS labels or an additional 16 octets for IPv6
+   address.
+
+       0                   1                   2                   3
+       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+      | Hash Key Type | Depth Limit   |  MP Index                     |
+      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+      |  IP Address or Next Label                                     |
+      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+      ....
+
+   The "Hash Key Type" determines the interpretation of the following
+   "IP Address or Next Label" fields.  The three formats of the "IP
+   Address or Next Label" are a 32 bit field containing an IPv4
+   address, a 32 bit field containing a LSB justified 20 bit MPLS
+   label with top 12 bits reserved for future use and set to zero, or
+   a 128 bit IPv6 address.
+
+    Hash Key Type:                         IP Address or Next Label
+    --------------                         ------------------------
+                 1   label                 1 or more label
+                 2   IPv4 address          1 or more IPv6 address
+                 3   label range           1 or more low/high label pairs
+                 4   IPv4 address range    1 or more low/high address pairs
+                 5   no more labels        (nothing)
+                 6   All IPv4 addresses    (nothing)
+                 7   no match              (nothing)
+		 8   IPv6 address	   1 or more IPv6 address
+		 9   IPv6 address range	   1 or more low/high address pairs
+		10   IPv4 bitmap	   see encapsulation below
+		11   label bitmap	   see encapsulation below
+		12   IPv6 bitmap	   see encapsulation below
+
+   The "Depth Limit" is applicable only to a label stack.  It gives
+   the maximum number of labels considered in the hash or zero for
+   unspecified or unlimited.
+
+   The "MP Index" is used to number the paths and provides a means to
+   refer to them.
+
+   The bitmap types each include a single IPv4 address, MPLS label, or
+   IPv6 address, followed by sets of four octets interpreted as 32 bit
+   words.  The IPv4 address, MPLS label, or IPv6 address should be the
+   first address equal to or numerically greater than the destination
+   address or label of the Echo Request with the lower 5 bits set to
+   zero (to avoid complex shift operations at a test ingress if the
+   union of bitmaps of multiple branch points must be determined).
+   Each bit starting with the least significant bit (MSB sent first)
+   is interpreted as one address.  A zero in a given bit position
+   indicates that the address or label will not exercise this path, a
+   one idicates that the path will be exercised.  The LSB of the first
+   32 bit word corresponds to the address or label provided.
+
+   Note that if a Downstream Multipath Mapping TLV cannot be fit in an
+   Echo Reply it is preferable to include less addresses or labels in
+   each Multipath Exercise TLV than omit information for some paths.
+
+3.5. Pad TLV
 
    The value part of the Pad TLV contains a variable number (>= 1) of
    octets.  The first octet takes values from the following table; all
    the other octets (if any) are ignored.  The receiver SHOULD verify
    that the TLV is received in its entirety, but otherwise ignores the
    contents of this TLV, apart from the first octet.
 
               Value        Meaning
               -----        -------
                   1        Drop Pad TLV from reply
                   2        Copy Pad TLV to reply
               3-255        Reserved for future use
 
-3.4. Error Code
+3.6. Error Code
 
    The Error Code TLV is currently not defined; its purpose is to
    provide a mechanism for a more elaborate error reporting structure,
    should the reason arise.

 4. Theory of Operation
 
 4.1. Sending an MPLS Echo Request
 
    An MPLS echo request is a (possibly) labelled UDP packet.  The IP
    header is set as follows: the source IP address is a routable address

@@ -791,24 +1032,170 @@

<prior diffs omitted>

+
+4.9 Exercising Multipath
+
+   A test traffic ingress upon receiving an Echo Reply containing a
+   Downstream Multipath Mapping TLV should try to exercise all paths
+   listed in the Downstream Multipath Mapping TLV.  If the "Type of
+   Multipath" is 1, indicating "per packet split", or 5, indicating
+   "other or unspecified", then random addresses in the range of 127/8
+   should be used.
+
+   If the "Type of Multipath" in the Downstream Multipath Mapping TLV
+   is 2-4, then for test traffic should be sent for each Multipath
+   Exercise TLV with a label stack or a destination address determined
+   to exercise each path.
+
+   When further testing an individual branch of a multipath, the
+   Downstream Multipath Mapping TLV in subsequent Echo Request packets
+   SHOULD contain only the Multipath Exercise TLV and Downstream
+   Mapping TLV for the path under test within the Downstream Multipath
+   Mapping TLV.
+
+   If an addtional multipath branch is encountered downstream of one
+   or more multipath branches, an intersection of the Multipath
+   Exercise TLV of the branches under test and each of the branches at
+   the new branch point must be determined.  If the intersection based
+   on the available information is the null set, each of the prior
+   branch points must be queried with the highest intersecting label
+   or address to obtain a new set of Multipath Exercise TLVs from a
+   different portion of label or address space.
+
+   For example, consider a case where one branchpoint under test has
+   returned a bitmap of address in the range 127.0.0.0-127.0.4.255, a
+   destination address 127.0.0.7 is used and a second branch point
+   returns a sparse bitmap covering 127.0.1.32-127.0.5.31, is
+   returned, and for a specific path from the second branch point,
+   there is no intersection between the two bitmaps.  An Echo Request
+   must then be sent with TTL set to deliver the packet to the first
+   branch point, with a destination address corresponding to the first
+   destination available in the second bitmap which was beyond the
+   range of the first bitmap.  This process is repeated until there is
+   an intersection in the returned bitmaps.  The intended path can now
+   be tested.
 
 5. Reliable Reply Path
 
    One of the issues that are faced with MPLS ping is to distinguish
    between a failure in the forward path (the MPLS path being 'pinged')
    and a failure in the return path.  Note that this problem exists with
    vanilla IP ping as well.  In the case of MPLS ping, it is assumed
    that the IP control and data planes are reliable.  However, it could
    be that the forwarding in the return path is via an MPLS LSP.
 
    In this specification, we give two solutions for this problem.  One
    is to set the Router Alert option in the MPLS echo reply.  When a