"Anonymous Networking with Minimum Latency in Multihop Networks"
P. Venkitasubramaniam and L. Tong
2008 IEEE Symposium on Security and Privacy, Oakland, CA, May 2008.

The problem of security against timing based traffic analysis in multihop networks is considered in this work. In particular, the relationship between the level of anonymity provided and the quality of service, as measured by network latency, is analyzed theoretically. Using an information theoretic measure of anonymity of routes in eavesdropped networks is considered, and packet scheduling strategies are designed to guarantee any desired level of anonymity. In particular, for individual relays, scheduling strategies based on mixing are designed so that the incoming and outgoing transmission epochs do not reveal any information. The proposed strategies utilize a limited fraction of dummy transmissions, and a significant reduction in packet latency at individual relays is demonstrated analytically for Poisson distributed arrivals. To minimize overall network latency, a randomized selection strategy is considered to choose the set of relays that use the designed scheduling strategies. The random selection is optimized for the desired level of anonymity using a well known distortion rate optimization in information theory. The tradeoff between overall network latency and anonymity in the network is characterized for centralized and decentralized scheduling strategies.