Electrical computers and digital processing systems: multicomput – Computer conferencing – Priority based messaging
Reexamination Certificate
1997-02-25
2001-11-27
Burgess, Glenton B. (Department: 2153)
Electrical computers and digital processing systems: multicomput
Computer conferencing
Priority based messaging
C709S240000
Reexamination Certificate
active
06324570
ABSTRACT:
FIELD OF INVENTION
This invention relates to prioritized delivery of information from a server to multiple clients and more particularly to a system which assures that all files will be delivered on time while at the same time minimizing waiting time for each individual client.
BACKGROUND OF THE INVENTION
As is often the case, a server is to deliver files to a multiplicity of clients. One of the bottlenecks to the efficient and complete transfer of large files from a server to a particular client, has to do with the bandwidth of the connection of the server to the network and the connection to each of the clients which also has a limiting bandwidth associated with it.
For instance, if a server has a relatively large file on the order of 10-100 megabytes, as is oftentimes the case, bandwidth constraints limit the simultaneous multicasting of this information to all of the clients. This means that the information must be sent to different clients at different times, meaning that only certain clients will be permitted to receive data at any given time. The problem is that the server may be unable to accommodate all clients at once. Moreover, while the server may be able to accommodate all the clients, it may not be able to make certain that a complete file will arrive by a certain due date. This means that the delivery of the information is not possible on a timely basis to all clients.
It is also a factor that not all the clients are on-line at any given time, so that attempting to send information to these clients results in wasted bandwidth.
The situation described above has become acute in view of the growth of so-called “push” technologies in which the server directly downloads to a particular client as opposed to receiving a request from a client. As a result, in the case of a single server which multicasts its data to a number of clients, the bandwidth of the server connection to the net and the bandwidth of the switch to the various clients are both limiting factors.
SUMMARY OF THE INVENTION
In order to accomplish efficient and robust delivery of large files from a single server to multiple clients, in the subject invention, the distribution of the information is prioritized such that clients are selected based on their ability to receive the information in a quick and efficient manner and also on the time left to meet a predetermined deadline for the transmission of the file. In one embodiment, the highest priority is given to those clients that are most in danger of not receiving an entire file by the predetermined deadline. On the other hand, priority is also given to minimize waiting time for a client by sending the information first to those clients having the fastest processors or, in general, the fastest network connection. For instance, for a client connected to the network at only 14 kilobytes per second, the connection is relatively slow. Thus initially those clients having connection speeds of 28.8 kilobytes or better are given priority.
Initially, the connection bandwidth priority dominates since the data transmission is routed to the faster connections. However, as time goes by, the deadline for the transmission of a file also approaches for clients having lower speed connections. At this point in time, it is necessary to download the file to those clients which are most in danger of the deadline not having been met.
An exponential curve-based algorithm is utilized to decide when, after initial transmission, the priorities are to be reset so as to assure that the slower connections will nonetheless have the file transmitted before the deadline.
It will be appreciated that the reason to give the highest initial priority to the fastest connections is to minimize the overall waiting time for the receipt of the information. If this was the only routine criteria, then only those clients having the faster connections would ever receive the complete files.
The uncertainty as to whether or not a complete file will in fact arrive on time is complicated by the log-in patterns of the various clients. As mentioned hereinbefore, it is of no utility to transmit data to a client who is off-line. Moreover, it is useful to consider the pattern of how long a client stays logged on once he has logged on in order to get an estimate of the probability of a successful transfer. Obviously, for those clients who stay logged on for a long period of time once they log on, the probability of a successful transfer increases, whereas for those clients who not only log-on infrequently, but then do not stay on-line, the probability for a transfer decreases.
For example, for those clients that log on frequently even though the log-on is for a short duration, assuming, for instance, a duty cycle of half, then the probability of a complete transfer to this client would be relatively high. On the other hand, a client that has the self-same one half duty cycle, but logs-on infrequently, depending on the time at which he is caught within his particular cycle, the result may be the inability to meet the deadline. Thus, for instance, even though in the second case the client logs on for four days and logs off for four days, indicating a long log on duration and a relatively high probability of successful transfer, if one attempts to transfer a file at the end of the four day period, the likelihood of a complete transmission is below that which would be associated with a one half cycle frequent user.
In order to calculate the probability of delivery, one assumes a normal distribution of the log-in duration of a user. The first step is to calculate the expected amount of time of the user's availability until the deadline, based on user's duty cycle and the average log-in duration.
More particularly, one calculates the distribution of the period that the user is expected to be logged-in until the deadline, which combined with the average throughput, allows one to calculate the probability of delivery.
Having derived the distribution curve, it is possible by inspection of the curve to ascertain beyond what point it would be impossible to effectuate the delivery and thus calculate the probability of success.
More specifically, files to be transmitted are coupled to a dispatch module which through the read-out of a statistics module are routed to the appropriate client. A priority evaluation model controls the dispatch model as to which clients are to receive the files at which time. The statistics module collects the statistics about a user based on past connections with the past connections, including average connection time, average log-in duration, average throughput and corresponding standard deviations. The average connection time or log-in duration refers to the average amount of time spent on-line, e.g. the average length of the log-in period. On the other hand, the average throughput refers to the average amount of data per second that can be sent to that particular client. The corresponding standard deviations refer to the standard deviations of these distributions. In the priority evaluation module, for each transfer of a File F with certain characteristics such as size of the file remaining to be transferred and the deadline for delivery, the priorities and their relationships are determined.
The result is provided to the dispatch module which determines which clients are to be serviced at any given point in time.
The result is a system which assures that data will be delivered on time to the maximum number of clients, while at the same time minimizing overall waiting time.
REFERENCES:
patent: 5369570 (1994-11-01), Parad
patent: 5440719 (1995-08-01), Hanes et al.
patent: 5586219 (1996-12-01), Yufik
patent: 5619647 (1997-04-01), Jardine
patent: 5623413 (1997-04-01), Matheson et al.
patent: 5694548 (1997-12-01), Baugher et al.
patent: 5737747 (1998-04-01), Vishlitzky et al.
patent: 5742772 (1998-04-01), Sreenan
patent: 5829046 (1998-10-01), Tzelnic et al.
patent: 5920700 (1999-07-01), Gordon et al.
Kobata Hiroshi
Tonchev Theodore G.
Burgess Glenton B.
e-Parcel, LLC
Fish & Richardson PC
Kupstas Tod
LandOfFree
Prioritized delivery and content auto select system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Prioritized delivery and content auto select system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Prioritized delivery and content auto select system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2605463