Multi-objective server placement determination

Patent metadata

Field	Value
Publication number	US-9083757-B2
Application number	US-201213684125-A
Country	US
Kind code	B2
Filing date	Nov 21, 2012
Priority date	Nov 21, 2012
Publication date	Jul 14, 2015
Grant date	Jul 14, 2015

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.

First claim

What is claimed is:

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 computing device 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

Assignees

• Ericsson Telefon Ab L M
• Ericsson Telefon Ab L M

Inventors

• Zhang Ying
• Li Du

Classifications

• H04L67/10

  in which an application is distributed across nodes in the network (software deployment G06F8/60; multiprogramming arrangements G06F9/46) · CPC title

• H04L67/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 title

• H04L12/1827

  Network arrangements for conference optimisation or adaptation · CPC title

• H04L67/52

  specially adapted for the location of the user terminal · CPC title

• H04L41/145 Primary

  involving simulating, designing, planning or modelling of a network · CPC title