Some open problems in P2P routing

Abstract

Combining problems of fixed infrastructure routing and routing around malicious nodes, this article discusses the theory of peer-to-peer routing in random geometric graphs. It investigates how global communication can be conducted in networks in which each node is connected to a small number of other nodes. The article identifies four main routing problems of increasing complexity, beginning with a scenario in which nodes are able to communicate with any neighbor. It then examines a setting in which routing must be resistant to denial-of-service attacks by a significant fraction of malicious nodes and explores a scenario in which routing must be performed purely locally, prohibiting the transmission of messages over long distances. The article concludes by presenting the most intricate problem of constructing a denial-of-service resistant routing protocol in a scenario with local communication. – AI-generated abstract.