Network bandwidth and object obsolescence sensitive scheduling method and apparatus for objects distributed broadcasting

• US 6,292,835 B1
• Filed: 11/26/1997
• Issued: 09/18/2001
• Est. Priority Date: 11/26/1997
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Huang, Yun-Wu, Yu, Philip Shi-Lung
• Primary Examiner(s): Luu, Le Hien
• Assistant Examiner(s): Prieto, Beatriz
• Application Number:
  US08/979,029
• Time in Patent Office: 1,392 Days
• Field of Search: 709/201, 709/102, 709/103, 709/218, 709/219, 709/229, 709/235, 709/118, 709/119, 370/232, 370/241, 370/234, 711/118, 711/119
• US Class Current: 709/235
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/26 using explicit feedback to the source, e.g. choke packets
• CPC Class Codes: H04L 67/01 Protocols
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/56 Provisioning of proxy services store-and-forward switching systems in data switching networks H04L12/54
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A proxy strategy not only caches objects but actively sets update schedules for channel information disseminated from different servers. Based on available bandwidth, this proxy strategy formulates a mathematical function that can be solved to establish the proxy update schedules by maximizing the overall currency of information received by the clients. Clients whose update requests do not result in receiving the most upto-date information for a given channel may also be recorded. After the next scheduled proxy update for a given channel, the proxy actively sends the most up-to-date information for this channel to the recorded clients. The client interest for a given channel is measured based on the client updates the proxy received since last scheduled update for this channel, and the currency of information received by these clients. A dynamic update can be performed by the proxy for channels with high client interest before their respective scheduled updates based on the available bandwidth. Upon performing a dynamic update for a given channel, the proxy can delay the next schedule update for this channel by a whole regular proxy update interval.

Claims

1. In a network comprising a plurality of servers which are each a source of data, a plurality of clients which each request data maintained in said servers, and a proxy which caches data received from said servers, a method for determining when to update data cached by said proxy, said method comprising the steps of:

receiving an indication of available network bandwidth between said plurality of servers and said proxy for performing updates of said data cached by said proxy;

receiving an indication of frequency with which at least one of said plurality of servers are updated;

maintaining a number of channels subscribed to by said clients and a channel size of each of the channels;

maintaining client request data, including a number of client requests for each of the channels;

deriving, from said indication of frequency and said client request data, obsolescence numbers associated with each channel, each of the obsolescence numbers reflecting the number of client requests for each channel that have received outdated data and reflecting how current said outdated data is; and

dynamically calculating when to update said data cached by said proxy based upon said indication of available network bandwidth and said obsolescence numbers.

2. The method of claim 1, wherein said indication of frequency is obtained from meta information transmitted by said at least one of said plurality of servers.

3. The method of claim 2, wherein said meta information is transmitted using at least one of meta data protocol CDF and meta data protocol MCF.

4. The method of claim 1, wherein a source of said updates of data cached by said proxy include at least one of said plurality of servers.

5. The method of claim 1, wherein the available network bandwidth comprises a total network bandwidth between the proxy and a portion of the network to which at least one of the plurality of servers is situated.

6. The method of claim 1, wherein the available network bandwidth comprises an allocation of a total network bandwidth between the proxy and a portion of the network to which at least one of the plurality of servers is situated, said allocation intended for update traffic.

7. The method of claim 1 further comprising the step of maintaining a maximum obsolescence threshold for each of the channels, wherein the calculating step further comprises the step of calculating when to update said data cached by said proxy further based upon at least one maximum obsolescence threshold.

8. The method of claim 1, further comprising the steps of:

receiving an indication of server updates not reflected by said proxy contents when at least one of said clients requests data from at least one of said servers; and

calculating when to update data cached by said proxy further based upon said indication of server updates.

9. The method of claim 1, further comprising the step of delaying updating of data cached by said proxy responsive to a decrease in data request from at least one of said clients.

10. A program storage device, readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for determining when to update data cached by a proxy, according to the method steps of claim 1.

11. In a network comprising a plurality of servers which are each a source of data, a plurality of clients which each request data maintained in said servers, and a proxy which caches data received from said servers, a method for providing an up-to-date version of cached data comprising the steps of:

receiving an indication of available network bandwidth between said plurality of servers and said proxy for performing updates of data cached by said proxy;

receiving an indication of frequency with which at least one of said plurality of servers are updated;

maintaining a number of channels subscribed to by said clients and a channel size of each of the channels;

maintaining client request data, including a number of client requests for each of the channels;

deriving, from said indication of frequency and said client request data, obsolescence numbers associated with each channel, each of the obsolescence numbers reflecting the number of client requests for each channel that have received outdated data and reflecting how current said outdated data is;

dynamically calculating when to update data cached by said proxy based upon said indication of available network bandwidth and said obsolescence numbers;

updating cached data based upon said calculating step;

determining whether a requesting one of said clients has received said up-to-date version of cached data;

providing said requesting one of said clients with available cached data when said requesting one of said clients makes said request; and

providing said requesting one of said clients with said up-to-date version of cached data when available.

12. The method of claim 11, further comprising the steps of:

maintaining a list of clients that have received cached data which differs from up-to-date data; and

providing said clients with said up-to-date data upon receipt by said proxy.

13. A program storage device, readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for providing an up-to-date version of cached data, according to the method steps of claim 11.

14. A proxy which caches data received from servers and which provides said data to clients responsive to requests from said clients for said data, said proxy comprising:

means for receiving an indication of available network bandwidth between said servers and said proxy for performing updates of data cached by said proxy;

means for receiving an indication of frequency with which at least one of said plurality of servers are updated;

means for maintaining a number of channels subscribed to by said clients and a channel size of each of the channels;

means for maintaining client request data, including a number of client requests for each of the channels;

means for deriving, from said indication of frequency and said client request data, obsolescence numbers associated with each channel, each of the obsolescence numbers reflecting the number of client requests for each channel that have received outdated data and reflecting how current said outdated data is;

and means for dynamically calculating when to update data cached by said proxy based upon said indication of available network bandwidth and said obsolescence numbers.

15. The proxy of claim 14, further comprising means for delaying updating of data cached by said proxy responsive to a decrease in data requests from at least one of said clients.

16. In a network comprising a plurality of servers which are each a source of data, a plurality of clients which each request data maintained in said servers, and a proxy which caches data received from said servers, a program storage device, readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for determining when to update data cached by said proxy, said method comprising the steps of:

receiving an indication of available network bandwidth between said plurality of servers and said proxy for performing updates of said data cached by said proxy;

receiving an indication of frequency with which at least one of said plurality of servers are updated;

maintaining a number of channels subscribed to by said clients and a channel size of each of the channels;

maintaining client request data, including a number of client requests for each of the channels;

deriving, from said indication of frequency and said client request data, obsolescence numbers associated with each channel, each of the obsolescence numbers reflecting accesses of each channel that have received outdated data and reflecting an outdatedness of said accesses; and

dynamically calculating when to update said data cached by said proxy based upon said indication of available network bandwidth and said obsolescence numbers.

17. In a network comprising a plurality of servers which are each a source of data, a plurality of clients which each request data maintained in said servers, and a proxy which caches data received from said servers, a program storage device, readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for providing an up-to-date version of cached data comprising the steps of:

receiving an indication of available network bandwidth between said plurality of servers and said proxy for performing updates of data cached by said proxy;

receiving an indication of frequency with which at least one of said plurality of servers are updated;

maintaining a number of channels subscribed to by said clients and a channel size of each of the channels;

maintaining client request data, including a number of client requests for each of the channels;

deriving, from said indication of frequency and said client request data, obsolescence numbers associated with each channel, each of the obsolescence numbers reflecting accesses of each channel that have received outdated data and reflecting an outdatedness of said accesses;

dynamically calculating when to update data cached by said proxy based upon said indication of available network bandwidth and said obsolescence numbers;

updating cached data based upon said calculating step;

determining whether a requesting one of said clients has received said up-to-date version of cached data;

providing said requesting one of said clients with available cached data when said requesting one of said clients makes said request; and

providing said requesting one of said clients with said up-to-date version of cached data when available.