Method and system for opportunistic broadcasting of data

We claim:

1. A method for downloading data from a server computer system to a plurality of client computer systems, the server computer system having a point-to-point transmission mechanism for receiving data from each client computer system, the server computer system also having a broadcast transmission mechanism for broadcasting data unidirectionally to the client computer systems, each client computer system having an identity and a broadcast receiver for receiving data broadcast by the broadcast transmission mechanism when the client computer system is in a receiving state, the method comprising the steps of:

under control of the server computer system,

selecting data to be downloaded from the server computer system to the plurality of client computer systems; and

broadcasting the selected data using the broadcast transmission mechanism;

under control of each client computer system in the receiving state,

receiving the broadcasted data; and

sending confirmation that the client computer system received the broadcasted data to the server computer system using the point-to-point transmission mechanism;

under control of the server computer system,

receiving the sent confirmations from the client computer systems and identifying those client computer systems that have sent confirmations; and

storing identities of those client computer systems that have sent confirmations:

under control of a client computer system that did not receive the broadcast of the selected data establishing a connection with the server computer system through the point-to-point transmission mechanism; and

under control of the server computer system,

determining that the client computer system that established the connection is not a client computer system that sent a confirmation by comparing the identity of the client computer system that established the connection with the stored identities of those client computer systems that have sent confirmations; and

in response to determining that the client computer system that established the connection is not a client computer system that sent a confirmation, transmitting the selected data to the client computer system that established the connection.

2. The method of claim 1 wherein the point-to-point transmission mechanism is also for transmitting data from the server computer system to each client computer system including the steps of:

under control of the server computer system and before the step of broadcasting the data,

determining whether to transmit the selected data to the client computer systems using the point-to-point transmission mechanism or using the broadcast transmission mechanism based on cost and timing considerations; and

when it is determined to transmit the selected data to the client computer systems using the point-to-point transmission mechanism, transmitting the selected data to each client computer system using the point-to-point transmission mechanism rather than broadcasting the data using the broadcast transmission mechanism.

3. The method of claim 1 including the steps of:

under control of each client computer system in the receiving state,

upon receiving the broadcasted data, determining whether the client computer system has established a connection with the server computer system through the point-to-point transmission mechanism; and

when no connection has been established, delaying the sending of the confirmation until a connection is established with the server computer system.

4. A method for ensuring receipt of data that is broadcast from a server computer system and received by a plurality of client computer systems, the server computer system having a broadcast transmission mechanism for transmitting data unidirectionally from the server computer system to the client computer systems, each client computer system having an identity and a broadcast receiver for receiving data broadcast by the broadcast transmission mechanism, the method comprising the steps of:

broadcasting the data using the broadcast transmission mechanism;

receiving at each of the plurality of client computer systems, the broadcasted data using the broadcast receiver;

upon receiving the broadcast data at a client computer system, sending a confirmation from the client computer system to the server computer system through a point-to-point transmission mechanism for sending data from client computer system to the server computer system; and

upon receiving by the server computer system a confirmation from a client computer system,

determining the identity of the client computer system that sent the confirmation; and

storing the identity of the client computer system that sent the confirmation so that the identity of a client computer system that did not receive the broadcast data and that subsequently establishes a connection with the server computer system can be compared with the stored identities to determine that the client computer system that subsequently establishes a connection with the server computer system did not receive the broadcast data.

5. The method of claim 4 including the steps of:

upon receiving the broadcasted data at each of the plurality of client computer systems,

determining whether the client computer system has a connection established with the server computer system through the transmission mechanism; and

when it is determined that no connection has been established, delaying sending the confirmation until a connection is established.

6. A method for downloading data from a server computer system to a plurality of client computer systems, the server computer system having a broadcast transmission mechanism and a point-to-point transmission mechanism, the broadcast transmission mechanism for transmitting data from the server computer system to the client computer system but cannot transmit data from the client computer systems to the server computer system, each client computer system having an identity and having a broadcast receiver for receiving data broadcast by the broadcast transmission mechanism, the point-to-point transmission mechanism being for transmitting data to and receiving data from each of the plurality of client computer systems, the method comprising the steps of:

determining broadcast transmission characteristics for the transmission of the data to be downloaded;

determining point-to-point transmission characteristics for the transmission of download data;

selecting whether to transmit the download data using the broadcast transmission mechanism or using the point-to-point transmission mechanism based on the determined transmission characteristics;

when the broadcast transmission mechanism is selected,

broadcasting the data to be downloaded using the broadcast transmission mechanism;

when the point-to-point transmission mechanism is selected,

sending the data to be downloaded to each client computer system using the point-to-point transmission mechanism;

receiving confirmations from client computer systems that received the broadcasted data;

identifying those client computer systems from which confirmations have been received:

storing identities of those client computer systems from which confirmations have been received; and

when confirmations have not been received from all the client computer system referencing the stored identities of those client computer systems from which confirmations have been received in order to determine those client computer systems that have not received the data and transmitting the data to those client computer systems that have not received the data using the broadcast transmission mechanism or using the point-to-point transmission mechanism.

7. The method of claim 6 wherein the step of transmitting the data to be downloaded to those client computer systems for which a confirmation has not been received is periodically repeated.

8. The method of claim 7 wherein the step of transmitting is periodically repeated until a confirmation from each client computer system is received.

9. The method of claim 7 wherein the step of transmitting is periodically repeated until a time out has occurred.

10. A method in a client computer system for confirming receipt of data broadcast by a server computer system, the broadcasted data being broadcasted using a broadcast transmission mechanism for transmitting data unidirectionally from the server computer system to the client computer systems, the method comprising the steps of:

when the client computer system does not have a connection established with the server computer system,

receiving the broadcasted data; and

storing an indication that the broadcasted data has been received; and

when the client computer system later establishes a connection with the server computer system using a bidirectional transmission mechanism,

checking for presence of the stored indication that the broadcasted data has been received; and

when the stored indication is present, sending a confirmation that the client computer system received the broadcasted data to the server computer system using the established connection

whereby the server computer system can track the client computer systems that have received the broadcasted data.

11. A computer-readable medium containing instructions for downloading data from a server computer system to a plurality of client computer systems, the server computer system having a point-to-point transmission mechanism for receiving data from each client computer system, the server computer system also having a broadcast transmission mechanism for broadcasting data unidirectionally to the client computer systems, each client computer system having a broadcast receiver for receiving data broadcast by the broadcast transmission mechanism when the client computer system is in a receiving state, by:

under control of the server computer system,

selecting data to be downloaded from the server computer system to the plurality of client computer systems; and

broadcasting the selected data using the broadcast transmission mechanism;

under control of each client computer system in the receiving state,

receiving the broadcasted data; and

sending confirmation that the client computer system received the broadcasted data to the server computer system using the point-to-point transmission mechanism; and

under control of the server computer system,

receiving the sent confirmations from the client computer systems;

storing indications that the sent confirmations have been received from the client computer systems; and

when a client computer system establishes a connection with the server computer system, transmitting the selected data to the client computer system if the server computer system has not stored an indication for that client computer system using the point-to-point transmission mechanism.

12. The computer-readable medium of claim 11 wherein the point-to-point transmission mechanism is also for transmitting data from the server computer system to each client computer system including:

under control of the server computer system and before broadcasting the data,

determining whether to transmit the selected data to the client computer systems using the point-to-point transmission mechanism or using the broadcast transmission mechanism based on cost and timing considerations; and

when it is determined to transmit the selected data to the client computer systems using the point-to-point transmission mechanism, transmitting the selected data to each client computer system using the point-to-point transmission mechanism rather than broadcasting the data using the broadcast transmission mechanism.

13. The computer-readable medium of claim 11 including:

under control of each client computer system in the receiving state,

upon receiving the broadcasted data, determining whether the client computer system has established a connection with the server computer system through the point-to-point transmission mechanism; and

when no connection has been established, delaying the sending of the confirmation until a connection is established with the server computer system.

14. A computer-readable medium containing instructions for causing a server computer system to transmit data from the server computer system to a plurality of client computer systems, by

broadcasting the data using a unidirectional transmission mechanism so that at least some of the client computer systems receive the data;

when a confirmation is received through a bidirectional transmission mechanism that a client computer system received the broadcasted data, storing an indication of such confirmation for the client computer system,

for each of the plurality of client computer systems,

establishing a connection with the client computer systeum using the bidirectional; transmission mechanism;

determining whether the client computer system has received the broadcasted data based on the stored indications; and

when it is determined that the client computer has not received the broadcasted data, transmitting the data using the bidirectional transmission mechanism to the client computer system.

15. The computer-readable medium of claim 14 wherein when a client computer system receives the broadcasted data, the client computer system sends a confirmation of receipt to the server computer system via the bidirectional transmission mechanism.

16. The computer-readable medium of claim 15 wherein the server computer system determines that a client computer system has not received the broadcasted data, when the server computer system has not received a confirmation from the client computer system.

Description Submit all comments and votes

TECHNICAL FIELD

This invention relates generally to a method and system for transmission of data and, more specifically, to a method and system of opportunistically broadcasting data or sending the data by a point-to-point connection.

BACKGROUND OF THE INVENTION

As computer systems become more and more common in the workplace and in the home, the demand for transmission of information between these computer systems is increasing. Many computer system are interconnected through networks such as the Internet. Although each computer system connected to such a network can receive data from and send data to each other computer system, there are difficulties in using such networks. For example, because such computer systems are based on the telephone network, data transmission typically occurs at a relatively slow transmission rate. Also, when the same data is to be sent to multiple computer systems, the same data must be transmitted multiple times, that is, once for each computer system that is to receive the data.

When many computer systems need to receive the same data, some computer systems broadcast the data using satellite transmission. With satellite transmission, the same data can be sent only once and received by many computer systems. Although satellite transmission rates are very fast, there are several disadvantages of transmitting data by satellite. First, the cost of transmitting data by satellite can be prohibitive. Second, the cost of each computer system is increased because each computer system needs a satellite receiver. Third, if a computer system is not running at the time of transmission, the computer system cannot receive the transmission. Consequently, satellite transmissions are often repeated at periodic intervals to ensure that each computer system receives the transmission. Of course, the repeating of such transmissions can be expensive and may be unnecessary because all computer systems, or least all those that care about the transmission, may have been running and actually received the data when it was first transmitted. Moreover, since such satellite transmissions typically only occur in one direction, there is generally no way of ensuring that all the intended recipient computer systems actually received a satellite transmission.

It would be desirable to have a transmission mechanism that would combine the advantages of the network computer systems and of satellite transmission, while minimizing their disadvantages.

SUMMARY OF THE INVENTION

The present invention provides method and system for opportunistically downloading data from a server computer system to client computer systems. The server computer system has a point-to-point transmission mechanism for receiving data from each client computer system and has a broadcast transmission mechanism for broadcasting data to the client computer systems. Each client computer system has a broadcast receiver for receiving data broadcast by the broadcast transmission mechanism when the client computer system is in a receiving state. In a preferred embodiment, the server computer system selects data to be downloaded from the server computer system to the client computer systems, and broadcasts the selected data using the broadcast transmission mechanism. Each client computer system that is in the receiving state receives the broadcasted data and sends a confirmation that the client computer system has received the broadcasted data to the server computer system using the point-to-point transmission mechanism. Conversely, when a client computer system enters the receiving state, it sends a request to send the selected data to the server computer system using the point-to-point transmission mechanism. The server computer system receives the sent request and transmits the selected data to the client computer system that sent the request when the server computer system has not received confirmation that the client computer system that sent the request received the broadcasted data.

Another aspect of the present invention provides a method and system for ensuring receipt of data that is broadcast from a server computer system and received by client computer systems. The server computer system has a broadcast transmission mechanism. Each client computer system has a broadcast receiver for receiving data broadcast by the broadcast transmission mechanism. The server computer system broadcasts the data using the broadcast transmission mechanism. Each client computer system uses the broadcast receiver to receive the broadcast data. Upon receiving the broadcasted data, each of client computer systems sends a confirmation from the client computer system to the server computer system through a transmission mechanism for sending data from client computer system to the server computer system.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a block diagram illustrating the components of the opportunistic broadcast system.

FIG. 2 is a diagram illustrating the operation of the opportunistic broadcasting system.

FIG. 3 is a block diagram illustrating the client APP, the client FTC and the client BDC.

FIG. 4 is a block diagram illustrating the server APP, server FTC, and the server BDC.

FIG. 5 is a flow diagram of the Message Loop of the client APP.

FIG. 6 is a flow diagram of the Received Download routine of the client FTC.

FIG. 7 is a flow diagram of the Global Receive thread of the client FTC.

FIG. 8 is a flow diagram of a sample Receive thread for the client FTC.

FIG. 9 is a flow diagram of the Receive Broadcast routine of the client BDC.

FIG. 10 is a flow diagram of the Register Address routine of the client BDC.

FIG. 11 is a flow diagram of the Message Loop of the server APP.

FIG. 12 is a flow diagram of the Request Download routine of the server APP.

FIG. 13 is a flow diagram of the Confirm Download routine of the server APP.

FIG. 14 is a flow diagram of the Request Download routine of the server FTC .

DETAILED DESCRIPTION OF THE INVENTION

The present invention provides a method and system for opportunistic broadcasting of data that is to be downloaded from a server computer system to client computer systems. In a preferred embodiment, a server computer system maintains a collection of data and can be connected to each client computer system through a point-to-point connection. The point-to-point connection can be via direct lines from each client computer system to the server computer system or via a routing network. Using the point-to-point connection, the server computer system can send data to and receive data from the client computer systems. However, if the same data is to be sent to multiple client computer systems using the point-to-point connection, the server computer system would send the same data multiple times: once for each client computer system. The server computer system also has a broadcasting transmission mechanism, such as a satellite, through which data can be broadcast to all client computer systems simultaneously. Each client computer system has a broadcast reception mechanism for receiving the broadcast data. Thus, when the same data is to be sent to multiple client computer systems, the server computer system can opportunistically broadcast the data and avoid sending the data once for each client computer system that is to receive the data. The server computer system sends the data via the broadcast transmission mechanism when it would be more efficient to do so.

In a preferred opportunistic broadcasting system of the present invention, the server computer system (server) receives a request from a client computer system (client) to download data from the server to the client computer system. The data is not only to be downloaded to the requesting client, but also to other clients who have not yet requested the data. The server may have received the data from a provider of data (e.g., contents of magazine) and a list of clients that are to receive the data. Alternatively, a client may have provided the data (e.g., electronic mail) that is to be sent to a list of clients. Also, the server may receive requests from many clients to download the same data. The server may group these multiple requests into a single download request that is to be downloaded to all the requesting clients. Before downloading the data to the requesting client, the server calculates certain transmission characteristics relating to the sending of the data to all the clients who are to receive the data using the point-to-point connection and using the broadcast mechanism. For example, the transmission characteristics may include transmission speed, cost of transmission, availability of the bandwidth for the transmission, and number of clients to whom the data is to be sent. The server uses these transmission characteristics to determine whether to transmit the data through the broadcast mechanism or through the point-to-point connection. For example, if the cost of transmitting through the broadcast mechanism is high and only two clients are to receive the data, then transmission through the point-to-point connection may be selected. Conversely, if the data is to be sent to 100 clients, then the cost of the 100 transmissions through the point-to-point connection may be higher than the cost of only one transmission through the broadcast mechanism. In this case, it may be cost-effective to broadcast the data. Thus, the opportunistic broadcasting system of the present invention selects the more efficient form of transmission based on the transmission characteristics.

When data is transmitted through the broadcast mechanism, not all the identified clients may be able to receive the broadcasted data. For example, a client computer system may be powered off at the time of the broadcast. The opportunistic broadcasting system uses a confirmation mechanism to ensure that each client eventually receives the data. The server tracks all those identified clients that have not yet confirmed receipt of the download data. When a client who has not confirmed receipt of the download data establishes a connection to the server through the point-to-point connection, the client may request the data to be downloaded. Typically, the server would send to the client a list of download data for which the client has not yet confirmed receipt. Using this list, the client can selectively request which data to download. To download the data again, the server again determines whether to transmit the data through point-to-point connection or through the broadcast mechanism. The server computer system makes this determination based on the transmission characteristics and the number of identified clients who have not yet confirmed receipt of the downloaded data. When the server re-transmits the download data for the clients who have not yet confirmed receipt, the server thus may again opportunistically broadcast the download data.

Many clients may be running at the time of broadcast, but may not be connected to the server at that time. These clients can receive and process the broadcasted data, but cannot confirm receipt of the broadcast. When such clients eventually connect to the server through the point-to-point connection, they can then confirm receipt of the download. Such clients would then typically request a list of data that the server has available to download to that client. However, since the client has confirmed receipt of some of the downloaded data, the list would not include that downloaded data. Thus, the client would have taken advantage of the broadcast of the data whose download was requested by another client.

FIG. 1 is a block diagram illustrating the components of the opportunistic broadcast system. The opportunistic broadcast system includes multiple client computer systems 101, a server computer system 102, broadcast transmission mechanisms 103A, 103B, point-to-point connection (PTP) 104, and a data provider 105. The client computer systems 101 include a client application (APP) 101A, a client File Transfer Component (FTC) 101B, a client Broadcast Data Component (BDC) 101C, a client PTP component 101D, and a broadcast receiver 101E. The server computer system 102 includes a server APP 102A, a server FTC 102B, a server BDC 102C, and a server PTP component 102D, and a broadcast transmitter 102E. The client computer systems can be connected to the server computer system through point-to-point connection 104. To broadcast data, the server computer system transmits the data to the broadcast mechanism 103A or 103B. In a preferred embodiment, the broadcast mechanism 103A is a satellite that receives transmissions from the broadcast transmitter 102E and broadcasts the transmissions to all broadcast receivers 101E simultaneously. Although the current preferred broadcast mechanism is satellite-based, the present invention can be used in conjunction with other types unidirectional broadcast mechanisms. For example, the computer systems may be connected to a cable television connection 103B, a high-speed fiber optic channel, or a radio-frequency channel on which data can be broadcast to all client computer systems simultaneously. The data provider computer system 105 provides data to the server for transmission to identified clients. The client APP and server APP represent application programs that request and receive download data. For example, the application program may be an electronic mail system. The client APP may represent the client portion of the mail system, and the server APP may represent the server portion of the mail system. The client APP and the server APP use the services of the client FTC and server FTC to download data. In a preferred embodiment, a client computer system can receive download data for a client APP even though the client APP is not currently executing and connected to the server APP. The client FTC and client BDC control the receiving of download data. If download data is received when the client APP is not executing, the data is stored until the client APP starts execution and retrieves the data.

Each transmission through the broadcast mechanisms includes information that identifies the client computer systems that are to receive the download data. Each client computer system is assigned a unique client identification number. The broadcast mechanism prefixes each transmission of download data with the client identifications of those client computer systems that are to receive the download data.

All client computer systems can receive all broadcasts of download data. However, only those client computer systems whose client identifications are included in the transmission will actually store and process the download data. The broadcast mechanism preferably uses an encryption mechanism to ensure that only the client computer systems to which the download data is being sent can store and process the download data. Each client computer system is assigned a public encryption key and a private decryption key. The server uses the public encryption key of the client to encrypt data that is to be sent to the client. Although all the clients can receive the encrypted data, only that client to which the data is directed can decrypt the data using its private decryption key.

The preferred broadcast mechanism uses "addresses," rather than client identification numbers when addressing a broadcast. Each client may be assigned its own address; in addition, a group of clients may be assigned to the same address. When a broadcast is addressed, each client that is assigned to that address can receive the download data. The broadcast mechanism need not be aware of the distinction between an address assigned to a single client or assigned to multiple clients. However, the server APP is preferably aware of each client that is assigned to an address. The server APP tracks whether all the clients assigned to an address have confirmed receipt of download data directed to the address. To ensure that the data sent to an address is received only by those clients who are assigned to that address, the server generates a public encryption key and a private decryption key for that address. Since each client assigned to an address needs access to the private decryption key to decrypt data sent to that address, the server sends the private decryption key to each assigned client. To send a private decryption key for an address to a client securely, the server encrypts the private decryption key using the public encryption key of the client before sending. Upon receiving the encrypted private decryption key of the address, the client uses its own private decryption key to decrypt the private decryption key of the address. In this way, only those clients that are assigned to an address have the private decryption key for that address. If new clients are assigned to the address, then the private encryption key for that address is sent to those new clients. If, however, clients are unassigned from the address, then a new public encryption key and private decryption key for the address is generated. The new private decryption key is sent to each client that is still assigned to the address. When data is sent to the address, it is encrypted with the new public encryption key. In this way, the client that was unassigned from the address can no longer decrypt the data for that address.

In one embodiment, the preferred broadcast mechanism allows addresses to be dynamically assigned. To allow this dynamic assignment, each client is assigned to a global address. The server broadcasts new address assignments on the global address. The broadcast includes the new address and the client identifications of each client assigned to the new address. Since each client processes data for the global address, each client will know whether it is assigned to the new address. Those clients that are assigned to the new address can then register to receive data on the new address. The assigned clients would also be sent a private decryption key for the new address. Alternatively, each client that is assigned to the new address can individually be notified using the client's own address rather than the global address.

FIG. 2 is a diagram illustrating the operation of the opportunistic broadcasting system. In this example, a client computer system receives a list of available data that the server computer system is prepared to download to the client computer system. In response, the client requests that the data be downloaded from the server computer system. The data that client A is requesting is also to be sent to client B, client C, client D, etc. In this example, the server opportunistically broadcasts the data to client A so that the other clients may also receive the data. As shown in step 201, client A sends a "request download" message to the server through the point-to-point connection. The message includes the identification of the data. When the server receives the "request download" message, the server recognizes that multiple clients are to receive the data and determines whether the data to be downloaded should be broadcast or sent through the point-to-point connection. In this example, the server decides to broadcast the data. The server first broadcasts to the global address that data will be transmitted on the identified address for clients A, B, C, D, etc. As shown in step 202, the server then broadcasts the data on the identified address, and the data is received by clients A, B, and C who were assigned to that address. The server assigns a download identification for the broadcast, which is transmitted with the broadcast. The clients who receive the broadcast use this download identification to confirm receipt of the download data. At the time of the broadcast, clients A and B were connected to the server, but client C was not connected. The computer system of client C, however, was running and thus able to receive the broadcast. The computer system of client D was not running and thus was unable to receive the broadcast. As shown in step 202, once client A receives the broadcast, it confirms receipt of the download by sending a "confirm download" message to the server. Upon receiving the "confirm download" message from client A, the server removes client A's identification from the list of clients who have not yet confirm the receipt of the download data. As shown in step 204, client B, who also received the download data and is connected to the server, sends a "confirm download" message to the server. Upon receipt of the "confirm download" message from client B, the server removes client B's identification from the list of clients who have not yet confirmed receipt of the download. As shown in step 205, client C was running, but was not connected to the server at the time of the broadcast. Although client C was not connected to the server, client C was able to process the data it received. When client C subsequently connects to the server, client C sends a "confirm download" message to the server. Upon receipt of the "confirm download" message, the server removes client C's identification from the list of clients who have not yet confirmed receipt of the download data. This confirmation is referred to as a "delayed confirmation" because although client C received the download data, it delayed sending the "confirm download" message until it was connected to the server through the point-to-point connection. As shown in step 206, client D eventually starts running and then connects to the server. Client D requests the server for a list of available data that is to be sent client D. The server determines that client D has not yet confirmed receipt of the download because its client identification is still in the list of clients. The server sends an indication to client D that it has this data for it. To download the data, client D then sends a "request download" message to the server. At that point, the server determines again whether the data to be downloaded should be broadcast or sent by the point-to-point connection to client D. In this example, the server decides to re-broadcast the data. As shown in step 207, when the data is re-broadcast the server uses the global address to identify the address to which the data will be sent and the clients who are to receive the data, and then broadcasts the data using the same download identification. Client D then receives the broadcast. As shown in step 208, client D sends a "confirm download" message to the server. The server removes client D from the list of clients. If a client had already received that download data, then it would disregard the re-broadcast. However, if a client had not received the initial broadcast, it would receive the re-broadcast, if running, and confirm receipt when it is connected to the server. Thus, the server can ensure that all the clients assigned to the address will eventually receive the download data or, at least, track those clients who have not yet confirmed receipt of the download data. Furthermore, the server can broadcast the data so that clients who have not yet requested the data to be downloaded can receive the data and avoid the overhead of requesting and retransmitting.

FIG. 3 is a block diagram illustrating the client APP, the client FTC, and the client BDC. The client APP represents a client application program that uses the services of the client FTC. The client APP receives a list of available data that may be downloaded, requests certain data be downloaded, receives the downloaded data, and confirms receipt of the downloaded data. During installation, the client APP registers the types of data that it would like to receive and designates the file directory in which it would like the data stored. The client FTC receives downloaded data, stores the data in the designated directory, an