Patent Document ID: 9420513
Application ID: 11767151
Patent Flag: 1

Claim One:
1. A clustering-based method of estimating a network metric for a pair of nodes of a plurality of nodes in a network, the method comprising: for each of the plurality of nodes, determining source clusters of nodes and destination clusters of nodes; selecting a cluster head for each cluster; storing measurements of the network metric between each node of the plurality of nodes and each cluster head for the source clusters and destination clusters for the node; and estimating, by a processor, the network metric for the pair of nodes of the plurality of nodes based on the measurements of the network metric for the pair of nodes, wherein for each of the plurality of nodes, determining source clusters of nodes and destination clusters of nodes comprises: for each node, performing traceroutes from the node to all other nodes of the plurality of nodes to determine paths to the all other nodes, wherein the paths include intermediate routers; determining a traceroute tree comprised of the determined paths; and determining k1 source clusters and k2 destination clusters based on a number of children from a root node in the tree and a number of leaves in subtrees for the children.