Anonymity is an essential asset for a variety of communication systems, like humans’ communication, the internet of things, and sensor networks. Establishing and maintaining such communication systems requires the exchange of information about their participants (called subjects). However, protecting anonymity reduces the availability of subject information, as these can be leveraged to break anonymity. Additionally, established techniques for providing anonymity often reduce the efficiency of communication networks. In this paper, we model four mechanisms to share routing information and discuss them with respect to their influence on anonymity and efficiency. While there is no one fits all solution, there are suitable trade-offs to establish routing information complying with the technical capabilities of the subjects. Distributed solutions like decentralized lookup tables reduce routing information in messages at the cost of local memory consumption; other mechanisms like multi-layer encrypted path information come with higher communication overhead but reduce memory consumption for each subject.