2005/07/14 by Ittai Abraham, Dahlia Malkhi, Abraham, Ittai +3
Computer Science · #Caching and Content Delivery #Cooperative Communication and Network Coding #Distributed #FOS: Computer and information sciences #Networking and Internet Architecture (cs.NI) #Parallel #Peer-to-Peer Network Technologies #and Cluster Computing (cs.DC) #cs.DC #cs.NI
paper · pdf · doi:10.48550/arxiv.cs/0507034
arxiv created 2005/07/14 · openalex publication_date 2005/07/14 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study \sc greedy routing over n nodes placed in a ring, with the distance between two nodes defined to be the clockwise or the absolute distance between them along the ring. Such graphs arise in the context of modeling social networks and in routing networks for peer-to-peer systems. We construct the first network over n nodes in which \sc greedy routing takes O(log n / log d) hops in the worst-case, with d out-going links per node. Our result has the first asymptotically optimal greedy routing complexity. Previous constructions required O((log2 n)/(d)) hops.