Recording observed and reported response characteristics at server and/or client nodes in a replicated data environment, and selecting a server to provide data based on the observed and/or reported response characteristics

• US 6,047,309 A
• Filed: 10/02/1995
• Issued: 04/04/2000
• Est. Priority Date: 10/02/1995
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Kienzle, Martin G., Tetzlaff, William H., Dan, Asit, Sitaram, Dinkar
• Primary Examiner(s): Chan, Eddie P.
• Assistant Examiner(s): KIM, HONG CHONG
• Application Number:
  US08/537,025
• Time in Patent Office: 1,646 Days
• Field of Search: 348/7, 395/200.01, 395/200.11, 395/835, 395/837, 395/838, 395/675, 709/201, 709/202, 709/203, 709/224-226, 709/223, 709/241, 709/105, 709/243
• US Class Current: 709/201
• CPC Class Codes: H04N 21/47202 for requesting content on demand, e.g. video on demand
• CPC Class Codes: H04N 7/17318 Direct or substantially direct transmission and handling of requests
• CPC Class Codes: H04N 7/17336 Handling of requests in head-ends

Abstract

A system and method for use in a distributed video-on-demand system of a type wherein at least one node provides blocks of video data to clients and wherein at least some of the blocks of video data are replicated on multiple nodes. Observed response characteristics for other nodes are recorded at least a given one of the nodes which serves a client requesting a replicated block. The given one of the nodes also records response characteristics reported to it by the other nodes. The node from which to fetch the replicated data block is selected based on which nodes include a copy of the replicated data block and based on at least one of the observed response characteristics and the reported response characteristics.

Claims

1. In a distributed server system of a type wherein at least one node provides data to at least one client and wherein at least some of the data is replicated on multiple nodes, a method for selecting a node to serve the data for provision to the at least one client, comprising the steps of:

recording observed response characteristics at a given node, of said multiple nodes and said at least one client, the observed response characteristics being response information concerning nodes in the server system as observed by the given node;

recording reported response characteristics, the reported response characteristics being response information concerning other nodes as reported to the given node by at least one other node in the distributed server system; and

,

selecting a node to serve replicated data based on which nodes include a copy of the replicated data and based on at least one of the observed response characteristics and the reported response characteristics.

2. The method of claim 1 wherein the reported response characteristics are sent to the given node as information piggybacked on other messages passed between the nodes.

3. The method of claim 1 wherein the observed characteristics include a measured delay in retrieving the data.

4. The method of claim 1 wherein the reported characteristics include a measure of performance of load on each node.

5. The method of claim 4 wherein the measure of performance is reported along with a time stamp indicative of when the measure was taken.

6. The method of claim 5 wherein the measure of performance is stored by the given node and wherein only the measure of performance having a most recent time stamp for each node is retained by the given node.

7. The method of claim 3 wherein the replicated block is retrieved from the node having the shortest measured delay.

8. The method of claim 1 wherein the observed response characteristics and the reported response characteristics are each given a weight and wherein the selecting is also based on the weight.

9. The method of claim 8 wherein the selecting is based on the response characteristics having the highest total weight.

10. The method of claim 1 comprising the further step of providing the replicated data to the at least one client.

24. The method of claim 1, wherein each of at least two of said multiple nodes and said at least one client node:

records observed response characteristics, the observed response characteristics being response information concerning nodes in the server system as observed by the respective one of said at least two nodes; and

records reported response characteristics, the reported response characteristics being response information concerning other nodes as reported to the respective one of said at least two nodes.

29. The method of claim 24, wherein the reported response characteristics are sent to said each of at least two nodes as information piggybacked on other messages sent to said nodes.

11. A distributed server system, comprising:

a plurality of nodes coupled by way of a first communication network;

a plurality of clients coupled to the plurality of nodes;

at least two of the plurality of nodes including a storage subsystem having replicated blocks of data stored thereon;

means in a given one, of the at least two nodes and the plurality of clients, for recording observed response characteristics, the observed response characteristics being response information concerning nodes in the server system as observed by the given one of the nodes;

means, in the given one of the nodes, for recording reported response characteristics, the reported response characteristics being response information concerning other nodes as reported to the given one of the nodes by at least one other nodes; and

,

means, in the given one of the nodes, for selecting a node to serve the replicated data block based on which of the nodes includes a copy of the replicated data block and based on at least one of the observed response characteristics and the reported response characteristics.

12. The system of claim 11 wherein each of the nodes having a replicated copy of the block includes means for sending the reported response characteristics to the given node as information piggybacked on other internode messages.

13. The system of claim 11 wherein the observed characteristics include a measured delay in retrieving the blocks.

14. The system of claim 12 wherein the reported characteristics include a measure of performance of load on each node.

15. The system of claim 14 wherein the means for sending include means for including a time stamp indicative of when the measure of performance was taken.

16. The system of claim 15 wherein the given node includes means for storing the measure of performance and for retaining the measure of performance having a most recent time stamp for each node.

17. The system of claim 15 wherein the means for selecting retrieves the replicated block from the node having the shortest measured delay.

18. The system of claim 11 wherein the observed response characteristics and the reported response characteristics are each given a weight and wherein the means for selecting selects the node at least in part based on the weight.

19. The system of claim 18 wherein the means for selecting, selects the node having the highest total weight.

25. The system of claim 11, wherein each of two given nodes, and the at least two nodes or the plurality of clients, includes:

means for recording observed response characteristics, the observed response characteristics being response information concerning nodes in the server system as observed by the respective one of said two given nodes; and

means for recording reported response characteristics, the reported response characteristics being response information concerning other nodes as reported to the respective one of said two given nodes.

30. The system of claim 25, wherein the reported response characteristics are sent to said each of said two given nodes as information piggybacked on other messages sent to said nodes.

20. In a server system of a type wherein at least one node provides blocks of data to clients and some of the blocks of data are replicated on multiple storage devices, a method for selecting a storage device from which to retrieve the data for provision to the clients, comprising the steps of:

recording observed response characteristics, the observed response characteristics being response information concerning performance of a plurality of the storage devices in the server system as observed by the at least one node;

recording reported response characteristics, the reported response characteristics being response information concerning the plurality of the storage devices as reported to the at least one node in the server system by computer processes managing the storage devices; and

,

selecting a storage device from which to retrieve the replicated data block based on which storage devices include a copy of the replicated data block and based on at least one of the observed response characteristics and the reported response characteristics.

26. The method of claim 20, wherein each of at least two nodes, including said at least one node, provides blocks of data to clients and some of the blocks of data are replicated on multiple storage devices in each of said at least two nodes, wherein each of said at least two nodes:

records observed response characteristics, the observed response characteristics being response information concerning performance of a plurality of the storage devices in the server system as observed by the respective one of said at least two nodes; and

records reported response characteristics, the reported response characteristics being response information concerning the plurality of the storage devices as reported to the respective one said at least two nodes by computer processes managing the storage devices.

31. The method of claim 26, wherein the reported response characteristics are sent to said each of at least two nodes as information piggybacked on other messages sent to said nodes.

21. A distributed computing system, comprising:

a plurality of nodes coupled by way of a first communication network;

a plurality of clients coupled to the plurality of nodes;

at least two nodes of the plurality of nodes including a storage subsystem having replicated blocks of data stored thereon;

a first table instantiated in a memory in a given one, of the plurality of nodes and the plurality of clients, dedicated to recording observed response characteristics, the observed response characteristics being response information concerning nodes in the system as observed by the given one of the nodes; and

,

a second table instantiated in the memory, dedicated to recording reported response characteristics, the reported response characteristics being response information concerning other nodes as reported to the given one of the nodes by at least one other node.

22. The system of claim 21 further comprising:

means, in the given one of the nodes, for selecting a node to serve the replicated data block based on which of the nodes includes a copy of the replicated data block and based on at least one of the observed response characteristics and the reported response characteristics.

27. The distributed computing system of claim 21, wherein first and second tables are instantiated in a memory in each of two given nodes of the plurality of nodes and the plurality of clients, for recording observed response characteristics concerning nodes in the system as observed by the respective one of the two given nodes and recording reported response characteristics concerning other nodes as reported to the respective one of the two given nodes by at least one other node.

32. The distributed computing system of claim 27, wherein the reported response characteristics are sent to said each of two given nodes as information piggybacked on other messages sent to said nodes.

23. A method of controlling a distributed computing system of a type wherein a plurality of nodes are coupled by way of a first communication network and wherein a plurality of clients are coupled to the plurality of nodes, at least two of the plurality of nodes having the capability of performing an identical function, comprising the steps of:

recording observed response characteristics at a given one, of the plurality of nodes and the plurality of clients, the observed response characteristics being response information concerning nodes in the system as observed by the given one of the nodes;

recording reported response characteristics, the reported response characteristics being response information concerning other nodes as reported to the given one of the nodes by at least one other nodes; and

,

selecting a node to perform the function based on which of the nodes can perform the function and based on at least one of the observed response characteristics and the reported response characteristics.

28. The method of claim 23, wherein each of two given nodes, of the plurality of nodes and the plurality of client nodes:

records observed response characteristics, the observed response characteristics being response information concerning nodes in the system as observed by the respective one of the two given nodes; and

records reported response characteristics, the reported response characteristics being response information concerning other nodes as reported to the respective one of the two given nodes by at least one other node.

33. The method of claim 28, wherein the reported response characteristics are sent to said each of two given nodes as information piggybacked on other messages sent to said nodes.