1. A network delay estimation apparatus that creates a metric tree describing delays among nodes of a network including a plurality of nodes, comprising; a first-round measurement target node selection section that selects one pair or a plurality of pairs of nodes located at a long distance from each other as first-round measurement target nodes from a known metric tree and measures a distance between an arbitrary node and each first-round measurement target node; a second-round measurement target node selection section that selects a node whose distance from the arbitrary node is estimated to be short as a second-round measurement target based on the distance from the first-round measurement target node and the known metric tree and measures a distance between the arbitrary node and each second-round measurement target node; and an optimum tree processing section that creates a metric tree of a network including the arbitrary node based on the distance from the second-round measurement target node and the known metric tree.