MULTI-OBJECTIVE SERVER PLACEMENT DETERMINATION

• US 20140143407A1
• Filed: 11/21/2012
• Published: 05/22/2014
• Est. Priority Date: 11/21/2012
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: LI, Du, ZHANG, Ying
• Granted Patent: US 9,083,757 B2
• Time in Patent Office: Days
• US Class Current: 709/224
• CPC Class Codes: H04L 12/1827 Network arrangements for conference optimisation or adaptation
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network
• CPC Class Codes: H04L 67/00 Network arrangements or protocols for supporting network services or applications user-to-user messaging H04L51/00; network arrangements, protocols or services for supporting real-time applications in data packet communications networks H04L65/00
• CPC Class Codes: H04L 67/01 Protocols
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 67/52 specially adapted for the location of the user terminal
• CPC Class Codes: H04L 67/535 Tracking the activity of the user network monitoring arrangements H04L43/00; recording of computer activity G06F11/34

Abstract

Methods and apparatus for determining recommended geographic server locations for online social networks by attempting to minimize user-server latency and inter-user communications latency. In an embodiment, geographic and relationship information for a plurality of users is acquired. The plurality of users may belong to one or more networks. The acquired information is transformed into a graph. A first plurality of clusters is generated with a first clustering algorithm. A second plurality of clusters is generated by iteratively examining pairs of the first plurality clusters, and swapping nodes between the examined clusters if it will reduce a total cut weight of the graph and locate each pair of nodes within a defined maximum distance from the centroid of the target cluster. In an embodiment, a method uses a joint analysis approach based upon characteristics of a plurality of existing networks.

Claims

1. A method in a computing device to determine a plurality of recommended geographic server locations by attempting to minimize both user-server latency and a latency of inter-user communications, the method comprising:

acquiring geographic information for a plurality of users of a set of one or more networks, wherein the geographic information for each of the plurality of users indicates a geographic location of that user;

acquiring relationship information for at least some of the plurality of users, wherein the relationship information indicates those of the plurality of users that are connected on a network of the set of networks;

transforming the geographic information and the relationship information into a graph including a plurality of nodes representing the plurality of users and a plurality of edges connecting the plurality of nodes according to the relationship information, wherein each of the plurality of edges includes an edge weight;

generating a first plurality of clusters by performing a first clustering algorithm on the graph, wherein each cluster of the first plurality of clusters includes a centroid and a set of one or more nodes of the plurality of nodes, wherein each of the set of nodes is included in only one of the first plurality of clusters;

generating a second plurality of clusters by performing a second clustering algorithm comprising,

iteratively examining pairs of clusters of the first plurality of clusters, and

for each examined pair of clusters, repeatedly swapping pairs of nodes between the pair of clusters when a swap of a pair of nodes will;

reduce a total cut weight of the graph, wherein the total cut weight is a sum of edge weights of edges that connect nodes in different clusters, and

locate each node of the pair of nodes, when swapped to the other cluster of the examined pair of clusters, within a defined maximum distance from the centroid of the other cluster to thereby bound user-to-server latency; and

causing information describing geographic locations of centroids of the second plurality of clusters to be presented to a user as the plurality of recommended geographic server locations.

2. The method of claim 1, wherein each of the edge weights indicates an estimated network latency time between those users of the plurality of users represented by the nodes at each end of the edge.

3. The method of claim 2, wherein the estimated network latency time is calculated by the server end station based upon Vincenty'"'"'s formula.

4. The method of claim 1, wherein:

the first clustering algorithm is based on either a k-means clustering algorithm or a k-medoids clustering algorithm; and

the first clustering algorithm uses known geographic locations of servers of at least one of the set of networks as initial centroid candidates.

5. The method of claim 1, wherein:

the count of the plurality of nodes is smaller than the count of the plurality of users; and

at least one of the plurality of nodes represents a group of two or more of the plurality of users.

6. The method of claim 5, wherein the group of users includes those of the plurality of users having the geographic location that is within a defined range of latitude and longitude values.

7. The method of claim 1, wherein:

a first plurality of the plurality of users are users of a first network of the set of networks; and

a second plurality of the plurality of users are users of a second network of the set of networks.

8. The method of claim 7, wherein the first network and the second network are online social networks.

9. The method of claim 1, wherein said transforming of the geographic information and the relationship information into the graph comprises:

transforming the geographic location of each user of the plurality of users into a latitude-longitude coordinate;

repeatedly aggregating those users of the plurality of users having latitude-longitude coordinates located within a defined distance of each other into one node to thereby create a plurality of nodes, wherein a weight of each node of the plurality of nodes indicates how many of the plurality of users are represented by that node;

connecting those of the plurality of nodes using a plurality of edges based upon whether any users aggregated by those nodes are connected as indicated by the relationship information; and

assigning a weight to each edge of the plurality of edges indicating the number of connections between those users of the plurality of users represented by the nodes of the plurality of nodes at each end of that edge.

10. A method in a computing device to determine a plurality of recommended geographic server locations by attempting to minimize both user-server latency and a latency of inter-user communications using a joint analysis approach based upon characteristics of a plurality of networks, the method comprising:

acquiring geographic information for a plurality of users of the plurality of networks, wherein the geographic information for a user of the plurality of users indicates a geographic location of the user;

acquiring relationship information for at least some of the plurality of users, wherein the relationship information indicates those of the plurality of users that are connected on at least one of the plurality of networks;

transforming the geographic information and the relationship information into a plurality of graphs, wherein each graph of the plurality of graphs represents one network of the plurality of networks and includes,

a plurality of nodes representing those users of the plurality of users that belong to the one network, and

a plurality of edges connecting the plurality of nodes according to the relationship information, wherein each of the plurality of edges includes an edge weight;

generating, for each graph of the plurality of graphs, a plurality of clusters for that graph by performing a clustering algorithm, wherein each of the plurality of clusters includes a centroid; and

identifying a first recommended geographic server location by;

ranking a set of centroids according to the frequency of occurrence of each centroid in the set of centroids, wherein the set of centroids includes all of the centroids of the plurality of clusters of each of the plurality of graphs, and

identifying a centroid of the ranked set of centroids having the highest occurrence as representing the first recommended geographic server location.

11. The method of claim 10, further comprising:

identifying a second recommended geographic server location by;

removing, from each of the plurality of graphs, all nodes from a cluster in that graph having a centroid located closest to the identified centroid to create a modified plurality of graphs,

for each of the modified plurality of graphs, generating a second plurality of clusters by again performing the clustering algorithm, wherein each of the second plurality of clusters includes a centroid,

ranking a second set of centroids according to the frequency of occurrence of each centroid in the second set of centroids, wherein the second set of centroids includes all of the centroids of the second plurality of clusters of each of the modified plurality of graphs, and

identifying a centroid of the ranked second set of centroids having the highest occurrence as the second recommended geographic server location.

12. The method of claim 10, wherein each of the edge weights indicates an estimated network latency time between those users of the plurality of users represented by the nodes at each end of the edge.

13. The method of claim 10, wherein the clustering algorithm is based upon a k-means clustering algorithm or a k-medoids clustering algorithm.

14. The method of claim 10, where the plurality of networks are online social networks.

15. A server end station to determine a plurality of recommended geographic server locations by attempting to minimize both user-server latency and a latency of inter-user communications, the server end station comprising:

an information acquisition module configured to,

acquire geographic information for a plurality of users of a set of one or more networks, wherein the geographic information for each user of the plurality of users indicates a geographic location of that user, and

acquire relationship information for at least some of the plurality of users, wherein the relationship information indicates those of the plurality of users that are connected on at least one network of the set of networks;

a transformation module configured to transform the geographic information and the relationship information into a graph including a plurality of nodes representing the plurality of users and a plurality of edges connecting the plurality of nodes according to the relationship information, wherein each of the plurality of edges includes an edge weight;

a server placement module configured to,

generate a first plurality of clusters by performing a first clustering algorithm on the graph, wherein each cluster of the first plurality of clusters includes a centroid and a set of one or more nodes of the plurality of nodes, wherein each node of the set of nodes is included in only one cluster of the first plurality of clusters, and

generate a second plurality of clusters by performing a second clustering algorithm comprising,

iteratively examining pairs of clusters of the first plurality of clusters, and

for each examined pair of clusters, repeatedly swapping pairs of nodes between the pair of clusters when a swap of a pair of nodes will;

reduce a total cut weight of the graph, wherein the total cut weight is a sum of edge weights of edges that connect nodes in different clusters, and

locate each node of the pair of nodes, when swapped to the other cluster of the examined pair of clusters, within a defined maximum distance from the centroid of the other cluster to thereby bound user-server latency; and

a presentation module configured to cause information describing geographic locations of centroids of the second plurality of clusters to be presented to a user as the plurality of recommended geographic server locations.

16. The server end station of claim 15, wherein the transformation module is configured to compute the edge weights by estimating a network latency time between those users of the plurality of users represented by the nodes at each end of the edge.

17. The server end station of claim 15, wherein:

the first clustering algorithm is based on either a k-means clustering algorithm or a k-medoids clustering algorithm; and

the first clustering algorithm uses known geographic locations of servers of at least one network of the set of networks as initial centroid candidates.

18. The server end station of claim 15, wherein the information acquisition module is configured to acquire said geographic information and said relationship information using a set of one or more network interface ports.

19. The server end station of claim 15, wherein:

a first plurality of the plurality of users are users of a first network of the set of networks; and

a second plurality of the plurality of users are users of a second network of the set of networks.

20. The server end station of claim 19, wherein the first network and the second network are online social networks.