Concilium: Collaborative Diagnosis of Broken Overlay Routes

In a peer-to-peer overlay network, hosts cooperate to forward messages. When a message does not reach its final destination, there are two possible explanations. An intermediate overlay host may have dropped the message due to misconfiguration or malice. Alternatively, a bad link in the underlying IP network may have prevented an earnest, properly configured host from forwarding the data. In this paper, we describe how overlay peers can distinguish between the two situations and ascribe blame appropriately. We generate probabilistic notions of blame using distributed network tomography, fuzzy logic, and secure routing primitives. By comparing application-level drop rates with network characteristics inferred from tomography, we can estimate the likelihood that message loss is due to a misbehaving overlay host or a poor link in the underlying IP network. Since faulty nodes can submit inaccurate tomographic data to the collective, we also discuss mechanisms for detecting such misbehavior.