The Address Resolution Protocol (ARP) is used by computers to map network addresses (IP) to physical addresses (MAC). The protocol has proved to work well under regular circumstances, but it was not designed to cope with malicious hosts. By performing ARP cache poisoning or ARP spoofing attacks, an intruder can impersonate another host (man-in-the-middle attack) and gain access to sensitive information. Several schemes to mitigate, detect and prevent these attacks have been proposed, but each has its limitations. In this paper we analyze each of these schemes, identify their strengths and weaknesses, and propose guidelines for the design of an alternative and (arguably) better solution to the problem of ARP cache poisoning.