Subject: Re: [pim] Benjamin Kaduk's Discuss on draft-ietf-pim-drlb-13: (with DISCUSS and COMMENT)

From: Benjamin Kaduk <[email-masked]>
Date: Fri, 3 Jan 2020 10:22:07 -0800

On Wed, Dec 18, 2019 at 10:22:39AM -0800, Stig Venaas wrote:
> Hi
> 
> Following-up on your discuss. Please see in-line. I've trimmed it down to
> what I understand is the remaining issue.

Thanks!

There's one point not in the quoted text that I'd like to dig into a little
more (as well as some more comments inline/at the end).

Specifically, now that the -14 has clarified that the mask bits do not need
to be contiguous, I wanted to double-check the procedure that is to be
applied, with respect to whether the "footprint" of the mask is (in
practice) limited to 32-bits wide or whether the mask is effectively
limited to 32 bits set total.  As a concrete example, consider the mask of
::f0f0:f0f0:f0f0:f0f0.  The LSZC of the mask is 4, so if I apply the
procedure to a group address ending in :3333:3333:3333:3333, do I mask to
get :3030:3030:3030:3030, shift to ...303030303030303, then mask with
0xffffffff to get 0x03030303 as input to the modulo operation?
Or do I *only* consider the bits set in the mask, so I mask to ...33333333,
mask again with 0xffffffff and use 0x33333333 as input to the modulo
operation?  My view is that the text is clearly saying the former, but some
comments in our other discussions suggested that perhaps the latter was a
possibility.  Can you please confirm which behavior is intended?

> On Mon, Dec 16, 2019 at 4:33 PM Benjamin Kaduk <[email-masked]> wrote:
> > > > ----------------------------------------------------------------------
> > > > DISCUSS:
> > > > ----------------------------------------------------------------------
> [...]
> > I do still worry some about the IPv6 limitation, though, but let me check
> > my understanding a bit.  It seems that we only take the low-order 32 bits
> > of the shifted+masked value out of implementation convenience, since 32-bit
> > integers are fast and (modular) division slow.  I'm not missing some more
> > fundamental reason why the 32 bits are chosen for the modulo hash
> > algorithm, am I?  (I mean, yes, IPv4 addresses will only populate 32 bits
> > of any field, but I am not sure why that length would have to be extended
> > to IPv6 processing, when zero-padding would produce a well-defined result.)
> 
> One significant reason for 32 bits, is that it is easy to compute modulo on any
> platform where this is likely to be implemented. The other perhaps not so
> good reason for 32 bit in particular is that it is easy to use the
> same algorithm
> as was used on IPv4 addresses once it is 32 bits. We also thought 32-bits
> were sufficient. See more details on that further down.
> 
> We could have folded the IPv6 address into 32 bits in such a way that the full
> address was being used, but we also wanted something where it is easy for
> an operator to predict the hashing.
> 
> > If it is just a relatively arbitrary choice of number of bits to take,
> > given that it in theory could have a detrimental effect on the mechanism
> > when used with IPv6, it would seem to potentially qualify as a "known
> > technical omission" in the language of RFC 2026, which is something that we
> > are not supposed to have in Proposed Standards.  Even if the IESG did
> > decide to waive the requirement, I think it would still be incubent upon us
> > to properly document the at-risk scenarios.
> 
> Let me comment further on while I don't see the 32 bits as a significant
> limitation. I want to add though, that the modulo algorithm has shortcomings
> in general, which is why we wanted to allow further hash algorithms to be
> defined in the future if needed. Among other things, such algorithms would
> not need to have the 32 bit limitation.
> 
> When people choose IPv6 multicast-group addresses, they tend to choose
> them so the least significant bits vary. RFC 3307 has the concept of a 32-bit
> group-ID that is used by IANA assignments, and should be used for dynamic
> assignments. One reason is that these 32 bits will also be used for link-layer
> multicast as mentioned in 3307.
> 
> Also when people allocate their own group addresses, from what I've seen,
> they typically use consecutive addresses, or least addresses where the less
> significant bits are not all the same. One way many choose IPv6 addresses
> that do not conflict with others, is unicast prefix-based addresses, RFC 3306,
> here a 32-bit group-ID is also used.
> 
> For SSM, source address is considered in addition to the group address. In
> the special case where many sources are sending to the same group, and
> few group addresses are used overall, it is important how the source
> address is hashed. Also here I would argue that people generally do manual
> assignments (or DHCP) where the least significant bits vary. Also if using
> SLAAC and EUI-64.
> 
> There are some special cases where people might have say the same
> unicast and multicast assignment schemes in multiple sites, and perhaps
> the multicast sources from different sites are identical except for some
> high-order bit in the addresses (e.g. with 3306 addressing, and for unicast
> addresses, unicast bits 32-47 might vary between sites, and multicast bits
> 64-79). For that, using hash masks that use those 32 bits would suffice.
> 
> If you in the same deployment have a significant number of flows that only
> vary in the lower bits, and also a significant number of flows that only vary
> in the higher bits (basically a combination of what I wrote first, and what
> I wrote in the above paragraph), then there is a problem. This seems fairly
> contrived to me though.

I agree that the known problematic scenarios seem fairly contrived.
Furthermore, if things change and non-contrived problematic scenarios
arise, we should be able to resolve them by simply defining a new
algorithm, so I don't feel a need to hold this document up and change the
algorithm right now.

> I hope this helps. Do you still think this limitation is strong enough to be a
> technical omission? If you like I can add some text in section 5.2.2
> pointing out this limitation.

I've cleared my Discuss position in the datatracker, but I would be more
comfortable if you do add a sentence in Section 5.2.2 noting that there is
this (probably hypothetical) limitation, and the workaround of defining a
new hash algorithm.

Thanks,

Ben

---

From: Stig Venaas <[email-masked]>
Date: Fri, 3 Jan 2020 14:15:24 -0800

Hi

Thanks for good input and clearing the discuss. I also posted version 15 to
address your comments. Please see my comments inline.

> possibility.  Can you please confirm which behavior is intended?

It is the former, 0x03030303 is the input in your example. So you pick at most
32 consecutive bits that will form the footprint.

> this (probably hypothetical) limitation, and the workaround of defining a

I added this paragraph to 5.2.2. I hope that addresses this. I agree it is
good to point this out. I couldn't find a crystal clear way to state it, but
I hope it is sufficient as it is not normative nor affecting implementations.

   The Modulo Hash Algorithm will use at most 32 consecutive bits of the
   input addresses for its computation.  Exactly which bits are used of
   the source, group or RP addresses, depend on the respective masks.
   This limitation may be an issue for IPv6 deployments, since not all
   bits of the IPv6 addresses are considered.  If this causes
   operational issues, a new hash algorithm would need to be defined.

Thanks and Happy New Year,
Stig

---

From: Benjamin Kaduk <[email-masked]>
Date: Fri, 3 Jan 2020 14:29:56 -0800

> address your comments. Please see my comments inline.

also inline

> 32 consecutive bits that will form the footprint.

Thank you; it gives me peace of mind to have it explicitly confirmed.

[...]
>    operational issues, a new hash algorithm would need to be defined.

I think it looks good (and being nonnormative is correct).

Thanks!

-Ben