2009/03/30 by Mohsen Ghaffari, Ghaffari, M., Behnoosh Hariri +3
Computer Science · #Computational Geometry (cs.CG) #Cooperative Communication and Network Coding #Energy Efficient Wireless Sensor Networks #FOS: Computer and information sciences #Mobile Ad Hoc Networks #Networking and Internet Architecture (cs.NI)
paper · pdf · doi:10.48550/arxiv.0903.5208
openalex publication_date 2009/03/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Large scale decentralized communication systems have introduced the new trend towards online routing where routing decisions are performed based on a limited and localized knowledge of the network. Geometrical greedy routing has been among the simplest and most common online routing schemes. A perfect geometrical routing scheme is expected to deliver each packet to the point in the network that is closest to the packet destination. However greedy routing fails to guarantee such delivery as the greedy forwarding decision sometimes leads the packets to localized minimums. This article investigates the necessary and sufficient properties of the greedy supporting graphs that provide the guaranteed delivery of packets when acting as a routing substrate.