Latency-based routing and load balancing in a network

• US 9,641,605 B2
• Filed: 06/30/2015
• Issued: 05/02/2017
• Est. Priority Date: 02/01/2012
• Status: Active Grant

• Current Assignee: TiVo Corporation (Adeia Inc.)
• Original Assignee: Comcast Cable Communications LLC (Comcast Corporation)
• Inventors: Patterson, Katherine E., Beenham, Nicholas C., Elamthuruthy, Joy Mathew
• Primary Examiner(s): Nguyen, Dustin
• Application Number:
  US14/755,731
• Publication Number:
  US 20150381715A1
• Time in Patent Office: 672 Days
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: H04L 43/0852 Delays
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/101 based on network conditions

Abstract

Aspects of the disclosure relate to routing queries to a network repository and load balancing in a network. For a network repository having a plurality of content storage sites, relative replication latency of data among a pair of content storages sites can be monitored. Data indicative of such replication latency can be distributed among the content storage sites and can be provided, for example, to a network node in a system layer. A traffic and control manager can determine routing pathways for queries based at least in part on the relative replication latency data and performance conditions of network nodes.

Claims

1. A method comprising:

receiving, at a first network node, data indicative of a plurality of relative lag times for instantiation of a specific content item at a first plurality of network nodes, the specific content item being common for each network node of the first plurality of network nodes;

receiving, at the first network node, network performance data related to servicing a request for the specific content item for each network node of a second plurality of network nodes;

receiving a request for the specific content item from at least one network node of the second plurality of network nodes;

selecting a network node of the second plurality of network nodes to service the request for the specific content item, the second network node of the second plurality of network nodes being configured based at least on the network performance data and a lag time for instantiation of the specific content item at a network node of the first plurality of network nodes associated with the second network node of the second plurality of network nodes; and

causing the second network node of the second plurality of network nodes to service the request.

2. The method of claim 1, wherein the network performance data comprises data indicative of one or more of a number of idle threads in a processor in a network node of the second plurality of network nodes, and memory utilization at the network node of the second plurality of network nodes.

3. The method of claim 1, wherein selecting the second network node of the second plurality of network nodes to service the request for the specific content item, comprises:

comparing network performance data of the second network node of the second plurality of network nodes to one or more service performance criteria; and

selecting the second network node of the second plurality of network nodes to service the request for the specific content item if the network performance data of the second network node of the second plurality of network nodes fulfills the one or more service performance criteria.

4. The method of claim 1, wherein selecting the second network node of the second plurality of network nodes to service the request for the specific content item, comprises:

comparing network performance data of the second network node of the second plurality of network nodes to one or more service performance criteria;

comparing network performance data of a third network node of the second plurality of network nodes to the one or more service performance criteria, wherein the third network node of the second plurality of network nodes transmitted the request for the specific content item; and

selecting the second network node of the second plurality of network nodes to service the request for the specific content item if the network performance data of the second network node of the second plurality of network nodes fulfills the one or more service performance criteria and the network performance data of the third network node of the second plurality of network nodes fails to fulfill the one or more service performance criteria.

5. The method of claim 1, further comprising redirecting the request for the specific content item to the second network node of the second plurality of network nodes.

6. The method of claim 1, wherein receiving, at the first network node, the data indicative of the plurality of relative lag times for instantiation of the specific content item at the first plurality of network nodes, comprises polling each one of the first plurality of network nodes for a data structure indicative of the plurality of relative lag times for instantiation of the specific content item, each of the first plurality of network nodes being a target node in a data replication topology.

7. The method of claim 1, further comprising providing, by each one of the first plurality of network nodes, an object identifier indicative of the network performance data to service the request for each network node of the second plurality of network nodes.

8. An apparatus comprising:

one or more processors; and

a memory comprising processor executable instructions that, when executed by the one or more processors, cause the apparatus to;

receive data indicative of a plurality of relative lag times for instantiation of a specific content item at a first plurality of network nodes, the specific content item being common for each network node of the first plurality of network nodes;

receive network performance data related to servicing a request for the specific content item for each network node of a second plurality of network nodes;

receive a request for the specific content item from at least one network node of the second plurality of network nodes;

select a second network node of the second plurality of network nodes to service the request for the specific content item, the second network node of the second plurality of network nodes being configured based at least on the network performance data and a lag time for instantiation of the specific content item at a network node of the first plurality of network nodes associated with the second network node of the second plurality of network nodes; and

cause the second network node of the second plurality of network nodes to service the request.

9. The apparatus of claim 8, wherein the network performance data comprises data indicative of one or more of a number of idle threads in a processor in a network node of the second plurality of network nodes, and memory utilization at the network node of the second plurality of network nodes.

10. The apparatus of claim 8, wherein the processor executable instructions that, when executed by the one or more processors, cause the apparatus to select the second network node of the second plurality of network nodes to service the request for the specific content item, further comprise processor executable instructions that, when executed by the one or more processors, cause the apparatus to:

compare network performance data of the second network node of the second plurality of network nodes to one or more service performance criteria; and

select the second network node of the second plurality of network nodes to service the request for the specific content item if the network performance data of the second network node of the second plurality of network nodes fulfills the one or more service performance criteria.

11. The apparatus of claim 8, wherein the processor executable instructions that, when executed by the one or more processors, cause the apparatus to select the second network node of the second plurality of network nodes to service the request for the specific content item, further comprise processor executable instructions that, when executed by the one or more processors, cause the apparatus to:

compare network performance data of the second network node of the second plurality of network nodes to one or more service performance criteria;

compare network performance data of a third network node of the second plurality of network nodes to the one or more service performance criteria, wherein the third network node of the second plurality of network nodes transmitted the request for the specific content item; and

select the second network node of the second plurality of network nodes to service the request for the specific content item if the network performance data of the second network node of the second plurality of network nodes fulfills the one or more service performance criteria and the network performance data of the third network node of the second plurality of network nodes fails to fulfill the one or more service performance criteria.

12. The apparatus of claim 8, wherein the processor executable instructions, when executed by the one or more processors, further cause the apparatus to redirect the request for the specific content item to the second network node of the second plurality of network nodes .

13. The apparatus of claim 8, wherein the processor executable instructions that, when executed by the one or more processors, cause the apparatus to receive the data indicative of the plurality of relative lag times for instantiation of the specific content item at the first plurality of network nodes, further comprise processor executable instructions that, when executed by the one or more processors, cause the apparatus to poll each one of the first plurality of network nodes for a data structure indicative of the plurality of relative lag times for instantiation of the specific content item, each of the first plurality of network nodes being a target node in a data replication topology.

14. The apparatus of claim 8, wherein the processor executable instructions, when executed by the one or more processors, further cause the apparatus to is further configured for providing, by each one of the first plurality of network nodes, an object identifier indicative of the network performance data to service the request for each network node of the second plurality of network nodes.

15. A method, comprising:

providing, by a first network node, control signaling among the first network node and a first plurality of network nodes configured in a data replication topology in a data layer;

receiving, by the first network node, data indicative of a plurality of relative replication latencies for instantiation of a specific data item at at least two of the first plurality of network nodes in response to the control signaling;

generating, by the first network node, a data structure comprising the data indicative of the plurality of relative replication latencies for instantiation of the specific data item;

receiving a request for the specific data item from at least one network node of a second plurality of network nodes;

selecting a second network node of the second plurality of network nodes to service the request for the specific content item, the second network node of the second plurality of network nodes being configured based at least on the network performance data and a lag time for instantiation of the specific content item at a network node of the first plurality of network nodes associated with the second network node of the second plurality of network nodes; and

causing the second network node of the second plurality of network nodes to service the request.

16. The method of claim 15, wherein providing, by the first network node, control signaling among the first network node and the first plurality of network nodes configured in the data replication topology in the data layer comprises periodically transmitting an instruction to supply data indicative of a relative replication latency for instantiation of the specific data item.

17. The method of claim 15, wherein generating, by the first network node, the data structure having the data indicative of the plurality of relative replication latencies for instantiation of the specific data item, comprises generating an off-diagonal matrix having matrix elements indicative of relative replication latency for instantiation of the specific data item among the second network node of the first plurality of network nodes and the at least one other network node of the first plurality of network nodes.

18. The method of claim 15, further comprising transmitting, by the first network node, each replication latency in the data structure to each of the first plurality of network nodes.

19. The method of claim 15, further comprising transmitting, by the first network node, each replication latency in the data structure to a network node of the second plurality of network nodes.

20. The method of claim 15, further comprising transmitting, by the first network node, data indicative of a relative replication latency for instantiation of the specific data item to a network node of the first plurality of network nodes in response to receiving the control signaling.