Latency-based routing and load balancing in a network

• US 9,106,663 B2
• Filed: 02/01/2012
• Issued: 08/11/2015
• 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:
  US13/363,996
• Publication Number:
  US 20130198368A1
• Time in Patent Office: 1,287 Days
• Field of Search: 709/223, 709/224, 709/225, 709/238, 707/634, 707/637
• US Class Current: 1/1
• 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; and

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

2. 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.

3. The method of claim 1, wherein the 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.

4. The method of claim 3, wherein polling comprises polling an off-diagonal matrix having matrix elements indicative of the plurality of relative lag times for instantiation of the specific content item.

5. The method of claim 1, wherein the second network node is selected in response to an indication that the network performance data of the second network node of the first plurality of network nodes fulfills a balancing criterion, and wherein the selecting comprises redirecting the request for the specific content item to the second network node.

6. 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 having 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; and

selecting a second network node of the first plurality of network nodes to service the request for the specific data item based at least on accessing the data structure to select the second network node of the first plurality of network nodes based on a first relative replication latency for instantiation of the specific data item at the second network node of the first plurality of network nodes with respect to a second relative replication latency for instantiation of the specific content at at least one other network node of the first plurality of network nodes.

7. The method of claim 6, 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.

8. The method of claim 6, 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 others network node of the first plurality of network nodes.

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

10. The method of claim 6, 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.

11. The method of claim 6, 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.

12. A system, comprising:

a first plurality of network nodes in an application layer;

a second plurality of network nodes in a data layer, wherein at least one network node in the first plurality of network nodes is configured to provide data indicative of a plurality of relative replication latencies of a specific data item at the second plurality of network nodes in the data layer; and

a first network node of the first plurality of network nodes in the application layer, the first network node being configured to;

receive network performance data of at least one network node of the second plurality of network nodes to service a request for the specific data item,

receive a request for the specific data item from at least one network node of the first plurality of network nodes, and

in response to the network performance data of at least one network node of the second plurality of network nodes being below a threshold, select a second network node of the second plurality of network nodes to service the request for the specific data item based at least on a first relative replication latency for instantiation of the specific data item at the second network node of the second plurality of network nodes with respect to a second relative replication latency for instantiation of the specific content at at least one other network node of the second plurality of network nodes.

13. The system of claim 12, wherein at least one network node of the second plurality of network nodes is further configured to provide an object identifier indicative of the network performance data to service the request for the specific data item.

14. The system of claim 13, wherein the object identifier is a simple network management protocol (SNMP) object identifier (OID).

15. The system of claim 12, 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, or memory utilization at the network node.

16. The system of claim 12, wherein at least one network node of the second plurality of network nodes is further configured to compose a data structure having data indicative of the plurality of relative replication latencies.

17. The system of claim 16, wherein the data structure is an off-diagonal matrix having matrix elements indicative of the plurality of relative replication latencies.

18. The system of claim 12, wherein each network node of the second plurality of network nodes is further configured to transmit at least a portion of the data structure to the first network node of the first plurality of network nodes.

19. The system of claim 18, wherein at least one network node of the first plurality of network nodes is an application server, the first network node of the first plurality of network nodes is a network load balancer, and at least one network node of the second plurality of network nodes comprises a database.