Gray hole attacks are a significant threat to mission critical communication infrastructures, such as industrial control systems. They are relatively easy to perpetrate, as an attacker that has access to communication links or equipment could observe the source and destination addresses for every message, and can identify and discard the messages exchanged between particular communication participants. Anonymity networks could render these attacks more difficult by providing anonymous communication via relaying. Nevertheless, relaying introduces overhead as it increases end-to-end message delivery delay and introduces additional traffic, which both in practice must often be low. Hence, an important question is how to optimize anonymity for limited overhead. In this paper we address this question by studying two anonymity networks: MCrowds, an extension of Crowds, which provides unbounded communication delay and Minstrels, which provides bounded communication delay. We derive exact analytical expressions for the relationship anonymity for these systems. Using MCrowds and Minstrels we show that, contrary to intuition, increased overhead does not always improve anonymity. We investigate the impact of the system’s parameters on anonymity and on the optimal anonymity network parameters, and the sensitivity of anonymity to the misestimation of the number of attackers.