Construct Optimal Diameter Network and d-partition Routing Algorithm

摘要

This paper studies the topological structure of network using graph-theoretical properties and proposes a topology construction method of regular directed graphs (or digraphs). The diameter of the topological digraph is [log_d n]. In this paper, we also propose a routing algorithm based this topological structure and find its complexity is O([log_d n]). This algorithm has a smaller diameter and easier to construct than the existing algorithms, which can be used of downloading files and defending worms in structured peer-to-peer systems.