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?

  • 3
    Time 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
    Commented 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.
    – Chris
    Commented Nov 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
    Commented Aug 10, 2017 at 23:21

1 Answer 1


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).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.