Traffic Mapping

• US 20200137148A1
• Filed: 10/31/2018
• Published: 04/30/2020
• Est. Priority Date: 10/31/2018
• Status: Active Grant

• Current Assignee: Twitter Inc (X Holdings Corp.)
• Original Assignee: Twitter Inc (X Holdings Corp.)
• Inventors: Segal, Todd, O'Brien, Nolan Daniel, Ho, Hanson, Xiong, Fei, Boyd, Brendan
• Granted Patent: US 10,999,358 B2
• Time in Patent Office: Days
• CPC Class Codes: H04L 43/0864 Round trip delays
• CPC Class Codes: H04L 43/10 Active monitoring, e.g. heartbeat, ping or trace-route
• CPC Class Codes: H04L 43/12 Network monitoring probes
• CPC Class Codes: H04L 65/612 for unicast
• CPC Class Codes: H04L 65/80 Responding to QoS
• CPC Class Codes: H04L 67/101 based on network conditions
• CPC Class Codes: H04L 67/1021 based on client or server locations
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching
• CPC Class Codes: H04N 21/222 Secondary servers, e.g. proxy server, cable television Head-end provisioning of proxy services in data packet switching networks H04L67/56
• CPC Class Codes: H04N 21/23106 involving caching operations prefetching while addressing of a memory level in which the access to the desired data or data block requires associative addressing means within memory systems or architectures G06F12/0862; caching at an intermediate stage in a data network H04L67/568

Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for providing to user devices identifiers of edge servers from which to obtain content. One example system includes a traffic control service. The traffic control service is configured to receive polling requests from user devices. In response to a particular polling request, the traffic control service obtains aggregated data about the user devices and edge servers. The traffic control service selects, based on the aggregated data, a best edge server for the user device that sent the particular polling request. The traffic control service sends an identifier of the selected best edge server to the user device.

Claims

1. A system comprising:

a plurality of user devices;

a plurality of edge servers configured to provide access to a content platform that serves content to the user devices, wherein each user device is associated with a network key, wherein the number of network keys is less than the number of user devices, and wherein each user device is configured to send requests for content to an edge server of the plurality of edge servers identified by data on the user device as a best edge server for the user device;

the user devices being configured to perform operations comprising;

sending probing requests to the best edge server for the user device and to one or more of the plurality of edge servers not identified as the best edge server,

receiving probing responses to the probing requests or noting a lack of response, and

determining, for each received probing response, a round-trip time, the round-trip time being an amount of time elapsed between a time the user device received the probing response and a time the user device sent the corresponding probing request, the determined round-trip times being edge server data; and

one or more services on the content platform configured to perform operations comprising;

obtaining from the user devices the edge server data, wherein the edge server data that is received from each user device is labeled with device information about the user device that provided the edge server data including the network key associated with the user device,

aggregating the edge server data by network key, and

in response to a polling request received from a user device;

selecting a best edge server for the user device based at least in part on the edge server data that had been aggregated by the network key that is the same as the network key associated with the user device, and

providing, to the user device, an identifier of the selected best edge server for the user device and identifiers of one or more other edge servers to which the user device should send future probing requests.

2. The system of claim 1, wherein the network key associated with each user device comprises (i) a country code of the user device and (ii) an autonomous system number corresponding to an Internet Protocol (IP) address of the user device.

3. The system of claim 1, wherein the network key associated with each user device comprises (i) a country code of the user device, (ii) an autonomous system number corresponding to an IP address of the user device, and (iii) the first three octets of the IP address of the user device.

4. The system of claim 1, wherein the network key associated with each user device comprises a country code of the user device, an autonomous system number corresponding to an IP address of the user device, an identifier of a network egress path of the user device, an identifier of a geographic region where the user device is located, and an identifier of a connection type of the user device.

5. The system of claim 1, wherein aggregating the edge server data by network key comprises, for each edge server:

determining a number of probing requests that were sent to the edge server by user devices associated with a same network key in a predetermined time window;

calculating a probing response success rate of the edge server, the probing response success rate being the number of probing responses received by user devices associated with the same network key divided by the number of probing requests sent to the edge server by the user devices; and

calculating a mean round-trip time of the edge server, the mean round-trip time of the edge server being a mean of the round-trip times determined for the probing responses sent by the edge server and received by the user devices associated with the same network key.

6. The system of claim 5, wherein selecting a best edge server for the user device based on the aggregated data comprises:

providing the aggregated data and identifiers of edge servers to a machine learning model, wherein the machine learning model is trained to identify best edge servers; and

receiving, from the machine learning model, an identifier of the best edge server for the user device.

7. The system of claim 5, wherein aggregating the edge server data by network key further comprises, for each edge server:

calculating a standard deviation of the round-trip times of the edge server to user devices associated with the same network key.

8. The system of claim 7, wherein selecting a best edge server for the user device based on the aggregated data comprises:

calculating, for each edge server that meets a predetermined minimum probing response success rate, a respective server score; and

identifying, as the best edge server, the edge server with a best server score.

9. The system of claim 8, wherein the server score corresponds to the mean round-trip-time of the edge server.

10. The system of claim 8, wherein the server score corresponds to a sum of the mean round-trip-time of the edge server and the standard deviation of the round-trip times of the edge server.

11. The system of claim 8, wherein the one or more other edge servers to which the user device should send future probing requests comprise a next 30 to 40 highest ranked edge servers based on the server scores of the edge servers.

12. The system of claim 8, wherein the one or more other edge servers to which the user device should send future probing requests is determined by:

selecting edge servers from among the edge servers with a server score by a virtual raffle in which each edge server with a server score is assigned a number of raffle tickets that is higher for edge servers with better server scores than other edge servers.

13. The system of claim 9, wherein the one or more services on the content platform are further configured to perform operations comprising:

obtaining throughput data from each of the plurality of edge servers, the throughput data comprising, for each edge server, a bit rate of the edge server; and

adjusting the server scores of the edge servers based on the throughput data.

14. The system of claim 1, wherein the one or more services comprise an aggregation service and a traffic control service, wherein:

the aggregation service is configured to perform operations comprising;

obtaining from the user devices the edge server data collected by the user devices, wherein the edge server data that is received from each user device is labeled with device information about the user device that provided the edge server data including the network key associated with the user device, and

aggregating the edge server data by network key,

the traffic control service is configured to perform operations comprising;

in response to a polling request received from a user device;

selecting a best edge server for the user device based on the edge server data that had been aggregated by the network key that is the same as the network key associated with the user device, and

providing, to the user device, an identifier of the selected best edge server for the user device and identifiers of one or more other edge servers to which the user device should send future probing requests.

15. A method comprising:

receiving a polling request from a first user device of a plurality of user devices, wherein each user device is configured to access a content platform through one of a plurality of edge servers identified by data on the user device as a best edge server for the user device, wherein each user device is associated with one of a plurality of network keys, and wherein the number of network keys is less than the number of user devices;

obtaining edge server data from the user devices, wherein the edge server data from each user device is labeled with device information about the user device including the network key associated with the user device, wherein the edge server data includes round-trip times that are computed by each user device by;

sending probing requests to the best edge server for the user device and to one or more of the plurality of edge servers not identified as the best edge server,

receiving probing responses to the probing requests or noting a lack of response, and

determining, for each received probing response, a round-trip time, the round-trip time being an amount of time elapsed between a time the user device received the probing response and a time the user device sent the corresponding probing request;

aggregating the edge server data by network key;

selecting a best edge server for the first user device based at least in part on the edge server data that was aggregated by the network key that is the same as the network key associated with the first user device, and

providing, to the first user device, an identifier of the selected best edge server for the user device and identifiers of one or more other edge servers to which the first user device should send future probing requests.

16. The method of claim 15, wherein the network key associated with each user device comprises (i) a country code of the user device, (ii) an autonomous system number corresponding to an IP address of the user device, and (iii) the first three octets of the IP address of the user device.

17. The method of claim 15, wherein aggregating the edge server data by network key comprises, for each edge server:

determining a number of probing requests that were sent to the edge server by user devices associated with a same network key in a predetermined time window;

calculating a probing response success rate of the edge server, the probing response success rate being the number of probing responses received by user devices associated with the same network key divided by the number of probing requests sent to the edge server by the user devices; and

calculating a mean round-trip time of the edge server, the mean round-trip time of the edge server being a mean of the round-trip times determined for the probing responses sent by the edge server and received by the user devices associated with the same network key.

18. The method of claim 17, wherein aggregating the edge server data by network key further comprises, for each edge server:

calculating a standard deviation of the round-trip times of the edge server to user devices associated with the same network key.

19. The method of claim 18, wherein selecting a best edge server for the first user device based at least in part on the aggregated edge server data comprises:

calculating, for each edge server that meets a predetermined minimum probing response success rate, a respective server score; and

identifying, as the best edge server, the edge server with a best server score.

20. One or more non-transitory computer storage media storing instructions that are operable, when executed by one or more computers, to cause the one or more computers to perform operations comprising:

receiving a polling request from a first user device of a plurality of user devices, wherein each user device is configured to access a content platform through one of a plurality of edge servers identified by data on the user device as a best edge server for the user device, wherein each user device is associated with one of a plurality of network keys, and wherein the number of network keys is less than the number of user devices;

obtaining edge server data from the user devices, wherein the edge server data from each user device is labeled with device information about the user device including the network key associated with the user device, wherein the edge server data includes round-trip times that are computed by each user device by;

sending probing requests to the best edge server for the user device and to one or more of the plurality of edge servers not identified as the best edge server,

receiving probing responses to the probing requests or noting a lack of response, and

determining, for each received probing response, a round-trip time, the round-trip time being an amount of time elapsed between a time the user device received the probing response and a time the user device sent the corresponding probing request;

aggregating the edge server data by network key;

selecting a best edge server for the first user device based at least in part on the edge server data that was aggregated by the network key that is the same as the network key associated with the first user device, and

providing, to the first user device, an identifier of the selected best edge server for the user device and identifiers of one or more other edge servers to which the first user device should send future probing requests.

21. The one or more non-transitory computer storage media of claim 20, wherein the network key associated with each user device comprises (i) a country code of the user device, (ii) an autonomous system number corresponding to an IP address of the user device, and (iii) the first three octets of the IP address of the user device.

22. The one or more non-transitory computer storage media of claim 20, wherein aggregating the edge server data by network key comprises, for each edge server:

determining a number of probing requests that were sent to the edge server by user devices associated with a same network key in a predetermined time window;

calculating a probing response success rate of the edge server, the probing response success rate being the number of probing responses received by user devices associated with the same network key divided by the number of probing requests sent to the edge server by the user devices; and

calculating a mean round-trip time of the edge server, the mean round-trip time of the edge server being a mean of the round-trip times determined for the probing responses sent by the edge server and received by the user devices associated with the same network key.

23. The one or more non-transitory computer storage media of claim 22, wherein aggregating the edge server data by network key further comprises, for each edge server:

calculating a standard deviation of the round-trip times of the edge server to user devices associated with the same network key.

24. The one or more non-transitory computer storage media of claim 23, wherein selecting a best edge server for the first user device based at least in part on the aggregated edge server data comprises:

calculating, for each edge server that meets a predetermined minimum probing response success rate, a respective server score; and

identifying, as the best edge server, the edge server with a best server score.