How does BranchCache avoid overloading LANs with Multicast discovery?

Network admins are screaming, network is overloaded, Broadcast storms are seen. (Please note that BranchCache does not use Broadcast but Multicast). Exponential concerns. Yada yada yada.

How do we answer all of these horrid accusations? Well, as always, we slap an algorithm in their faces. (Note: We are no longer allowed to write that they should be taken out the back door and given a good beating - by order of 2Pint marketing).

Lets dig straight into it.

BranchCache is a clever clogs, it's got your back. BranchCache in Distributed mode uses the WSD protocol (small multicast messages) to find peers with content. There are two modes of operations in WSD: client-initiated Probes and service-initiated announcements; both are sent through IP multicast to a predefined group. The PCCR Discovery Protocol uses the client-initiated Probes to query peer nodes for content.

A higher level

The Microsoft name for the protocol built on top of WSD for finding peers is called PCCR Discovery Protocol, PCCRDP in short for, or Peer Content Caching and Retrieval Discovery Protocol in it’s long format. As we said earlier, this is based on the Web Services Dynamic Discovery (WS-Discovery, WSD for short) protocol. It is a content caching and retrieval framework based on a peer-to-peer discovery and distribution model. It’s an open protocol.

In the PCCR Discovery Protocol the peers looking for content are the WSD clients, sending out multicast WSD Probe messages with the hashes of the content. The peers that are serving the content take the server role of WSD, listening to Probes and replying to the querying clients with unicast

WSD ProbeMatch messages if the content hashes match the ones that are cached locally. To avoid the situation where multiple server peers overwhelm a client with ProbeMatch messages, per the WS-Discovery protocol, each server peer waits for a backoff timer to expire before sending the ProbeMatch. The value of the backoff timer is set randomly between 1 millisecond and a maximum back-off time.

Client peer

We learned here from the protocol docs, that a client peer acts as the following:

The client peer MUST set a request timer when sending a Probe message to wait for a certain period of time for the incoming replies. The request timer is configurable such that system administrators can adjust the value based on their current network environments. The default value of the request timer is in the range of 200 milliseconds to 500 milliseconds, and under all circumstances, the waiting period SHOULD NOT be smaller than the maximum backoff timer value to ensure that enough replies are received by a requesting peer. When the request timer expires on a requesting peer without receiving any ProbeMatch replies, the implementation MUST remove that Probe message and its associated HoHoDk List from the Outstanding Probe List.

Ok, so we basically run on default here, seems to be good enough, lets move on.

Serving peers

From the docs, we get that the server peer does the following:

The server peer MUST set a backoff timer (defined and explained in [WS-Discovery]) randomly between 1 millisecond and a maximum value (defined by the WSD Protocol constant APP_MAX_DELAY). If the server peer has the requested segment IDs in the request, the server MUST send the ProbeMatch message back to the requesting peer when the backoff timer expires. If the server peer does not have the requested segment IDs, the server MUST ignore the request. For a detailed description of the backoff timer, see [WS-Discovery]. This timer is configurable such that system administrators can adjust the value based on their current network environments. By default, APP_MAX_DELAY SHOULD be set to 65 milliseconds.

Ok, so we have some spread, but not too much smartness, what's going on?

Don’t shout all at once kids – we had you on HoHoDk

So how do we protect against overloading requesting peers then? Surely there must be the case of one query and a thousand replies. No, not really, but it depends, on a lot.

To answer or not to answer - that is the question. There is of course smartness built in, but how does it work?

The following rules are used to determine whether a server peer will reply to a Probe message when it has the requested segment. Keep in mind, a server peer was/is also a client peer, so it knows stuff too, potentially.

When the server peer first requests and downloads a segment as a client, it records the number of replies it receives and whether the replies contain the entire segment or just a portion of the segment. Later, when the server peer receives a Probe message for that segment, it proceeds as follows (where n is an administratively configurable parameter with the default value n = 10):

• If there were fewer than n replies, the server peer will respond to the new Probe after the backoff timer expires.
• If there were at least n replies:
  • If there were at least n full-segment replies, the server peer will not reply to the new Probe.
  • If there were fewer than n full-segment replies, the server peer will randomly determine whether to reply to the new Probe, with a probability of 0.33 for replying.

So, basically, if you are deploying a new piece of data to a lot of machines, will there be a lot of queries going out? The answer is: potentially maybe. So if BITS is doing the download, the job is NOT in FOREGROUND, then we will get an automatic ~10s of all clients sending out the same initial short lists of hashes, as they see each other, they form a flash crowd. For anyone that doesn’t know what that is, here is a video to refresh the memory: https://www.youtube.com/watch?v=cxLbmnvMWM0 (which is pretty much how a download with BranchCache would be portrayed, like music).

So, then going as a FlashCrowd, the back offs are much longer, and basically lowering the overall speed of the downloads, lowering the impact on the network. If clients are spread over time instead, as more and more clients are coming in there wont be much increase in the response, as the algorithm above 10 full segment replies (basically 10 clients responding), this leads to a large number of clients will NOT reply to requests (as there are still other ones doing that).

So, typically, BranchCache is not too bad on the network, even under heavy load. It’s more likely that your network people are complaining about Delivery Optimization ARP Broadcast message. But that's a whole other story!

Drop mic!