Patent ID: 8812663

Claim:
A network delay estimation apparatus that creates a metric tree describing delays among nodes of a network including a plurality of nodes, comprising: a processing unit having a plurality of sections configured to execute steps of a control program; a storage memory medium configured to store the steps of the control program; a first-round measurement target node selection section configured to select from a known metric tree a pair of nodes located at a longest distance from each other as a pair of first-round measurement target nodes and to measure distances between a joining node whose position with respect to the network is unknown and each of the first-round measurement target nodes; a second-round measurement target node selection section configured to estimate a node whose distance from the joining node is estimated to be shortest based on the distances between the joining node and each of the first-round measurement target nodes, to select the estimated node as a second-round measurement target node, and to measure a distance between the joining node and the second-round measurement target node; and an optimum tree processing section configured to create a new metric tree including the joining node based on the first-round measurement target nodes, the second-round measurement target nodes, and the known metric tree, wherein the second-round measurement target node selection section is configured to estimate a node at a position having a shortest distance from a path connecting the first-round measurement target nodes to be the node having a shortest distance from the joining node, further comprising a candidate tree creation section configured to create candidate trees with the joining node added to the known metric tree based on the first-round measurement target nodes and the second-round measurement target node selected based on the first-round measurement target nodes, and wherein: the optimum tree processing section is configured to determine, out of the candidate trees, a candidate tree containing fewer errors with respect to measured values of each distance between the joining node and the first-round measurement target nodes and the second-round measurement target nodes to be the network metric tree including the joining node.