Is it valid to say that the complexity of ARP requests in a broadcast domain increases squared to the number of participants, as in the worst case every participant wants to address every other participant in the domain?
-
3Time is a very relevant factor here, without taking that (and ARP caching) into account this is impossible to answer properly. Also, since there should be traffic between nodes, if one ARPs for the other and traffic passes, the other sides learns it as well. So the upper limit of ARP's needed is roughly 0.5*n*(n-1) if all nodes need to communicate with eachother at the same time with empty ARP caches. However, while typing this I'm really wondering what actual problem you're trying to solve here.– Teun Vink ♦Nov 22, 2014 at 16:04
-
Thanks for your comment. Yes, I came to the same worst case formula, and with n going to infinity, this is a squared type complexity. I am looking for a "mathematically proper" explanation why it makes sense to split broadcast domains. So when adding devices with similar network usage to a broadcast domain, normal point-to-point traffic will increase linear, but the worst-case effort to link them first (ARP) will increase squared.– ChrisNov 23, 2014 at 11:06
-
Did any answer help you? if so, you should accept the answer so that the question doesn't keep popping up forever, looking for an answer. Alternatively, you could provide and accept your own answer.– Ron Maupin ♦Aug 10, 2017 at 23:21
1 Answer
Yes, ARP is quadratic in the worst case. This is the case of every flat routing protocol (and ARP can be seen as a degenerate routing protocol) — in order to get sub-quadratic scaling, you need some form of route summarisation.
If this is actually a problem on your network, you should either split it into multiple networks connected by layer 3 routers (which can be seen as performing summarisation), or change your application to use multicast (which doesn't need ARP).