RE: Comments on draft-yourtchenko-colitti-nd-reduce-multicast

[Andrew Yourtchenko <[e-mail]>]

Hemant,

On Fri, 21 Feb 2014, Hemant Singh (shemant) wrote:

>> If you're not convinced, then you can skip this item for your 
>>deployment. I've seen it once, and there were multiple contributing 
>>factors, so I don't have a good data to convince you. Equally I don't 
>>have a spare lab with >9000 hosts of various operating systems, moving 
>>around. I left it because it does seem like a conservatively prudent 
>>thing to do.
>
> It's not me.  Each time anyone has contacted the IETF mailers such as 
>the 6man or the v6ops WG for an avalanche problem with IPv6 ND or DHCPv6, 
>folks in the WG's have replied that both ND and the DHCPv6 specifications 
>have randomization and at least ND has an additional jitter that avoids 
>avalanches to cause any major problem in the ipv6 network.  I have 
>personally tested routers with over 40,000 IPv6 clients with a router

Were they 802.11 clients ? Wireless medium does have different properties.
Did you make any "flash failure" events ? Anyway, see below.

>reload and did not see avalanche issues with ND nor DHCPv6.   Sorry, 
>there was a typo in my email that said "not" when I should have said 
>"lot".    I am interested to know why one client in a 100K client 
>deployment has lot of IPv6 entries in the client Neighbor Cache?  How 
>much is a lot?  10, 100, 1000 and how are these entries populated in the 
>client?

Myself I did not like this portion of my reply with no quantifiable data 
(because operating on a basis of a belief is not a good engineering).

I happened to have a couple of hours of offline time, during which I tried 
to sketch the scenario and try to get as far as I can without building a 
lab.

It's a *very rough sketch*. If you think there can be parts that can be 
made better in it, tell me.

The initial assumptions for this thought experiment are as follows:

1) We have 10000 clients in a single /64.

2) There are multiple APs that bridge the traffic from wired onto
wireless medium, with the client count limited to 100 per AP.

3) there is 20x speed difference between unicast transmission and
multicast transmission.: the effective multicast speed is assumed to be
1 mbps, the effective unicast speed is assumed to be 20mbps data rate.

4) The APs are assumed to be "Naive" i.e. they do not perform any snooping
nor multicast->unicast conversions, but at the same time they are able to 
bridge the unicast traffic without flooding it between multiple access 
points. I.e. we assume a model where we have a single router (or an FHRP 
pair) and a set of 100 APs bridging the traffic.

(Corollary from the above: The effective unicast capacity is 100*20mbps, 
whereas the effective multicast capacity is 1*1Mbps, therefore the difference in 
throughput is 1000-fold).

Let's first consider the steady state. Suppose each host downloads
a file at 0.1 mbps.  Within each AP, therefore we have a 50% capacity 
utilization (0.1*100 = 10Mbps, we have 20 Mbps capacity).

It's easy to see this comfortably accomodates all the hosts. Obviuously
the unicast NUD in this traffic is fairly minimal, so I don't think it's 
even worth to count how much it is.

Now, lets look at a potential failure.

At the time of the NUD probe, it's enough to lose the 3 retries,
spaced 1 second apart.  The default reachable time is 30 seconds,
with the random jitter of 0.5 of that.

So, all that is needed to achieve a mass NUD failure is a ~30 second
outage during the period when all the hosts are sending the traffic.

A reboot of the majority of the networking gear takes several times longer 
than this.

Therefore, a crash of the default gateway during the peak hour is
a one guaranteed trigger for this to happen.

So, now we have a situation of 10000 hosts which have deleted their 
default gateway from the neighbor table, and send the multicast neighbor 
solicitations for it.

Assume the NS is 64 bytes, 10000 hosts sending such a packet means 64 
bytes * 8 bit * 10000 hosts = 5120000 bits/sec - or, 5 mbps.

Note, that this is only the shared bandwidth downstream back to the hosts 
- the airtime spent by the upstream traffic is 20x faster, so I am 
gratuitously discarding it.

Since the APs can not send the traffic at this rate, obviously, we will
need to drop some of it. Note, if the clients succeed with the ND to the 
default gateway, they will start streaming data again, so the effective 
multicast throughput will drop to the 0.5 mbps as soon as the noticeable 
portion of clients recovers.

Let's assume the best case of 20% of the clients managing to recover 
within the first second.

As we are approaching full recovery, the lesser number of clients will be 
able to get their multicast NS sent because the airtime is being taken by 
the payload traffic. Anyway, let's discard that and assume that every 
second 20% of the clients will recover.

This means that the recovery of the full set of the clients in this 
conditions will take an *absolute* minimum of 5 seconds.

Did I prove myself wrong ? Seems so. We can see that with some of 
the relaxed assumptions I took, the hosts seem to recover.

But, let's add to this a little bit of mDNS, and other multicast-loving 
protocols, which tend to generate a fair chunk of traffic when they detect 
the network was "restored".

This can shrink the available capacity several times. Add to this 
that the host does not necessarily stream at 100kbps, but might have 
higher data rates, and I think we can consider the available
multicast capacity at startup to be 1/10th of what it is in theory.

This is where the things may become interesting - 1/10th of the 
capacity means that it will take not 5, but 50 seconds for all the 
hosts to recover.

This means that the hosts which recovered in the very first second, will 
already be sending NUD traffic while the network is still under stress. If 
these packets are lost, the hosts might back into the pool of the 
"orphans" who are sending the multicast, because they delete their 
neighbor entry.

There are some other things to consider:

- I deliberately kept the scenario here with *one* ND entry.
Assuming your hosts are talking with 3-4 other hosts besides the default 
gateway. This increases the load and proportionally makes the dangerous 
state easier to achieve.

- another factor that I am omitting - that such a storm of ND 
onto the default gateway might cause rate-limiting of the control plane 
packets on the gateway. With some of the limits being as low as 1000pps, 
this might give a recovery time on the order of minutes even without the 
wireless multicast being the bottleneck, yet still resulting in a lot 
of multicast NS in the air still during the slow recovery.

This is about as precise of the construct I can build.

Is it perfect ? No, by no means. It also does assume that in the case of 
the default gateway the wireless performance will be limiting factor - I 
think it won't - so it's more of an appropriate scenario for a case of a 
p2p communications on the network. The default-gateway-only will be 
inherently much more stable, I think - because the multicast on the wired 
side is fast, so the drops on the wireless side will not matter.

It's probably worth it to change the text into "There is potential for the 
failing NUD to *contribute* to a longer recovery and possible creation of 
the locked situation in the case of flash failure - but the exact 
quantification of the impact in such an environment is a topic of further 
study".

And then maybe I could dump the above thought experiment into a separate 
draft, to see if the folks could contribute to the experiment / maybe 
someone could run it - and reference it in this item ?

It seems like an interesting area to dig a bit more in - creating a 
suitable model and playing with the parameters to see where it breaks 
seems like a useful exercise to understand how many hosts can there be in 
a single /64 on WiFi with a "naive" set of access-points.

Thoughts ?

--a