Routing internet communications using network coordinates
View Patent ↗A communication technique includes routing communications over an internet topology using coordinates, which correspond to estimated round trip times, of an origination, a destination and at least one intermediary host or node. A disclosed example includes identifying candidate intermediary nodes based upon selected criteria such as proximity to at least one of the origination or destination for the communication. A disclosed example includes identifying a plurality of intermediary nodes for some applications.
1. A method of communicating on the internet, comprising
routing at least one communication from an origination to a destination through at least one intermediary node using synthetic coordinates of at least one of the origination or the destination and synthetic coordinates of the at least one intermediary node, wherein the synthetic coordinates and the routing are independent of a physical location of the nodes; and
selecting the at least one intermediary node from a plurality of candidate nodes that have a preselected relationship with at least one of the origination or the destination, wherein the preselected relationship comprises the candidate nodes being within a selected pattern in a corresponding coordinate space including the at least one of the origination or the destination in terms of the coordinates.
2. The method of claim 1 , comprising
determining the coordinates of the at least one intermediary node and the destination.
3. The method of claim 2 , wherein the coordinates of the origination are known and comprising selecting the intermediary node based upon the determined coordinates of the at least one intermediary node satisfying a selected criteria.
4. The method of claim 3 , wherein the selected criteria comprises a distance in terms of the coordinates that minimizes a total distance from the origination to the at least one intermediary node and from the at least one intermediary node to the destination.
5. The method of claim 3 , wherein the selected criteria comprises a minimized round trip time between the origination and the destination.
6. The method of claim 1 , wherein the selected pattern comprises an ellipse having the origination and the destination as the foci of the ellipse.
7. The method of claim 1 , wherein the selected pattern comprises a circle having the origination as the center.
8. The method of claim 1 , wherein the selected pattern comprises a circle having the destination as the center.
9. The method of claim 1 , comprising selecting a plurality of intermediary nodes.
10. The method of claim 1 , comprising selecting the at least one intermediary node such that it is at least one of close to the origination in terms of the coordinates, close to the destination in terms of the coordinates, between the origination and the destination in terms of the coordinates or close to both of the origination and the destination in terms of the coordinates.
11. The method of claim 1 , wherein at least the intermediary node is part of an overlay network.
12. The method of claim 11 , wherein each of the origination, destination and the intermediary node are part of an overlay network.
13. The method of claim 1 , comprising
selecting a plurality of candidate intermediary nodes;
measuring a communication travel time between each of the selected candidate intermediary nodes and at least one of the origination or the destination; and
identifying a most desired intermediary node from the selected plurality based at least in part on the measured times.
14. The method of claim 1 , wherein the routing comprises multicast routing.
15. The method of claim 1 , comprising
establishing a multicast tree using the synthetic coordinates; and
allowing cluster-heads of the multicast tree to forward communications only to other cluster-heads of the multicast tree.
16. A method of communicating on the internet, comprising
routing at least one communication from an origination to a destination through at least one intermediary node using synthetic coordinates of at least one of the origination or the destination and synthetic coordinates of the at least one intermediary node;
grouping a plurality of nodes into a plurality of groups that each have a centroid such that the nodes within one of the groups are close to each other in terms of the synthetic coordinates;
determining a centroid of each of the groups;
determining which of the nodes within each group is closest to the centroid in terms of the synthetic coordinates; and
using the determined closest node in each group as a cluster-head of the corresponding group.
17. The method of claim 16 , comprising
grouping a plurality of the cluster-heads into a plurality of second groups that each have a centroid such that the cluster-heads within one of the groups are close to each other in terms of the synthetic coordinates;
determining a centroid of each of the second groups;
determining which of the cluster-heads within each second group is closest to the corresponding centroid in terms of the synthetic coordinates; and
using the determined closest cluster-head in each second group as a second cluster-head of the corresponding second group.
18. The method of claim 17 , comprising repeating the grouping and determining steps until all participating nodes are connected in a multicast tree.