Time-window-constrained multicast using connection scheduling

• US 7,085,848 B2
• Filed: 03/15/2002
• Issued: 08/01/2006
• Est. Priority Date: 03/15/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Cabrera, Luis Felipe, Padmanabhan, Venkata N.
• Primary Examiner(s): Dharia, Rupal
• Assistant Examiner(s): Nguyen, Quang N.
• Application Number:
  US10/099,251
• Publication Number:
  US 20030177183A1
• Time in Patent Office: 1,600 Days
• Field of Search: 709/203, 709/224, 709/232, 709/247, 713/178, 725/97, 725/101, 370/432
• US Class Current: 709/232
• CPC Class Codes: H04L 67/01 Protocols
• CPC Class Codes: H04L 67/101 based on network conditions
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A method of reducing bandwidth limitations to send events to a set of interested clients within a pre-defined time period as quickly and fairly as possible. The clients can be re-distributed among the servers in a network such that the delay due to server overloading is minimized by moving clients from an overloaded server to a server with available bandwidth. In addition, the latency of client-server communications can be incorporated into an estimation of download times, and the servers can then initiate delivery to respective clients based on those download times. By staggering the send times to account for heterogeneous latencies, more clients can receive the event at the same time, and a fairness of distribution can be achieved.

Claims

1. A method of distributing a client among a first trusted edge server and a second trusted edge server, wherein a trusted edge server is a server, in a communications path between an originating server and a connected client, that can be trusted not to release information prior to an appropriate time, the method comprising:

determining a first latency between the first trusted edge server and the client;

determining a second latency between the second trusted edge server and the client;

comparing the first latency to the second latency; and

transferring the client to the second trusted edge server if the second latency is lower than the first latency, further comprising;

obtaining a release time, wherein the release time is an earliest time at which an event is intended to be delivered to the client;

obtaining a completion time, wherein the completion time is a latest time at which the event can arrive at the client;

calculating a send time as a function of the first latency and the second latency; and

sending the event to the client at the send time.

2. A method of distributing an event from a trusted edge server to a client, wherein the trusted edge server is a server, in a communications path between an originating server and a connected client, that can be trusted not to release information prior to an appropriate time, the method comprising:

obtaining a release time, wherein the release time is an earliest time at which the event is intended to be delivered to the client;

obtaining a completion time, wherein the completion time is a latest time at which the event can arrive at the client;

determining a first latency between the trusted edge server and a first client;

calculating a first send time as a function of the first latency; and

sending the event from the trusted edge server to the client at the first send time, wherein the step of calculating the first send time further comprises;

estimating a first delivery time using the first latency; and

calculating the first send time to be prior to the completion time minus the first delivery time.

3. The method of claim 2, wherein the step of determining the first latency further comprises:

estimating the first latency using a connection history between the trusted edge server and the first client.

4. The method of claim 2, wherein the step of determining the first latency further comprises:

estimating the first latency using network functions to test a connection between the trusted edge server and the first client.

5. The method of claim 2, wherein the step of calculating the first send time further comprises:

estimating a first delivery time using the first latency; and

calculating the first send time as the release time minus the first delivery time.

6. The method of claim 2, wherein the event is distributed from the trusted edge server to a second client, the second client having a second latency, wherein calculating the first send time as a function of the first latency includes calculating the first send time as a function of the second latency, the method further comprising:

sending the event from the trusted edge server to the second client at the first send time.

7. The method of claim 6, wherein the step of calculating the first send time further comprises:

estimating a first delivery time as a function of the first latency;

estimating a second delivery time as a function of the second latency;

calculating the first send time to be equal to the release time minus the first delivery time if the second delivery time is greater than the first delivery time; and

calculating the first send time to be equal to the release time minus the second delivery time if the first delivery time is greater than the second delivery time.

8. The method of claim 6, wherein the step of calculating the first send time further comprises:

estimating a first delivery time as a function of the first latency;

estimating a second delivery time as a function of the second latency;

calculating the first send time to be prior to the completion time minus the first delivery time if the first delivery time is greater than the second delivery time; and

calculating the first send time to be prior to the completion time minus the second delivery time if the second delivery time is greater than the first delivery time.

9. The method of claim 2 further comprising:

determining a second latency between the trusted edge server and a second client;

calculating a second send time as a function of the second latency; and

sending the event from the trusted edge server to the second client at the second send time.

10. The method of claim 9, wherein the originating server distributes the event to the trusted edge server, the method further comprising:

determining an originating latency between the originating server and the trusted edge server;

calculating an originating send time as a function of the first send time, the second send time, and the originating latency; and

sending the event from the originating server to the trusted edge server at the originating send time.

11. The method of claim 2, wherein the originating server distributes the event to the trusted edge server, the method further comprising:

determining an originating latency between the originating server and the trusted edge server;

calculating an originating send time as a function of the first send time and the originating latency; and

sending the event from the originating server to the trusted edge server at the originating send time.

12. The method of claim 2, wherein:

determining the first latency includes;

determining a transfer latency;

comparing the first latency to the transfer latency; and

transferring the first client to a second trusted edge server if the transfer latency is lower than the first latency;

calculating the first send time includes determining the first send time as a function of a second latency between the second trusted edge server and the first client; and

sending the event includes sending the event from the second trusted edge server to the first client at the first send time if the transfer latency is lower than the first latency.

13. The method of claim 12, wherein the transfer latency is a latency between the second trusted edge server and the first client.

14. The method of claim 12, wherein the transfer latency is a minimum theoretical latency.

15. A method of distributing an event from a trusted edge server to a client, wherein the trusted edge server is a server, in a communications path between an originating server and a connected client, that can be trusted not to release information prior to an appropriate time, the method comprising:

obtaining a release time, wherein the release time is an earliest time at which the event is intended to be delivered to the client;

obtaining a completion time, wherein the completion time is a latest time at which the event can arrive at the client;

determining a first latency between the trusted edge server and a first client communicating with the first trusted server;

comparing the first latency to a first transfer latency;

transferring the first client if the first transfer latency is lower than the first latency;

calculating a first send time as a function of the first latency and the first transfer latency; and

sending the event to the first client at the first send time, wherein the first transfer latency is a latency between a second trusted edger server and the first client and wherein transferring the first client if the first transfer latency is lower than the first latency includes transferring the first client to the second trusted edger server.

16. The method of claim 15, wherein the event is distributed from a second trusted edge server to a second client, and wherein calculating the first send time as a function of the first latency and the first transfer latency includes calculating the first send time as a function of a second latency and a second transfer latency, the method further comprising:

determining the second latency between the second trusted edge server and the second client;

comparing the second latency to the second transfer latency;

transferring the second client if the second transfer latency is lower than the second latency; and

sending the event to the second client at the first send time.

17. The method of claim 16, wherein the second trusted edge server is the first trusted edge server.

18. The method of claim 16, wherein the step of calculating the first send time further comprises:

estimating a first delivery time as a function of the first latency and the first transfer latency;

estimating a second delivery time as a function of the second latency and the second transfer latency;

calculating the first send time to be prior to the completion time minus the first delivery time if the first delivery time is greater than the second delivery time; and

calculating the first send time to be prior to the completion time minus the second delivery time if the second delivery time is greater than the first delivery time.

19. The method of claim 15, wherein the event is distributed from a second trusted edge server to a second client, the method further comprising:

determining a second latency between the second trusted edge server and the second client;

comparing the second latency to a second transfer latency;

transferring the second client if the second transfer latency is lower than the second latency;

calculating a second send time as a function of the second latency and the second transfer latency; and

sending the event to the second client at the second send time.

20. A computer-readable medium, having computer-executable instructions for distributing an event from a trusted edge server to a client, wherein the trusted edge server is a server, in a communications path between an originating server and a connected client, that can be trusted not to release information prior to an appropriate time, the computer-executable instructions for performing steps comprising:

obtaining a release time, wherein the release time is an earliest time at which the event is intended to be delivered to the client;

obtaining a completion time, wherein the completion time is a latest time at which the event can arrive at the client;

determining a first latency between the trusted edge server and a first client;

calculating a first send time as a function of the first latency; and

sending the event from the trusted edge server to the client at the first send time, wherein the step of calculating the first send time further comprises;

estimating a first delivery time using the first latency; and

calculating the first send time to be prior to the completion time minus the first delivery time.

21. The computer-readable medium of claim 20, wherein calculating the first send time as a function of the first latency includes calculating the first send time as a function of a second latency between the trusted edge server and a second client, the computer-readable medium having further computer-executable instructions for performing steps comprising:

sending the event from the trusted edge server to the second client at the first send time.

22. The computer-readable medium of claim 21, wherein the step of calculating the first send time further comprises:

estimating a first delivery time as a function of the first latency;

estimating a second delivery time as a function of the second latency;

calculating the first send time to be prior to the completion time minus the first delivery time if the first delivery time is greater than the second delivery time; and

calculating the first send time to be prior to the completion time minus the second delivery time if the second delivery time is greater than the first delivery time.

23. The computer-readable medium of claim 20, having further computer-executable instructions for performing steps comprising:

determining a second latency between the trusted edge server and a second client;

calculating a second send time as a function of the second latency; and

sending the event from the trusted edge server to the second client at the second send time.

24. A computer-readable medium, having computer-executable instructions for distributing an event from a trusted edge server to a client, wherein the trusted edge server is a server, in a communications path between an originating server and a connected client, that can be trusted not to release information prior to an appropriate time, the computer-executable instructions for performing steps comprising:

obtaining a release time, wherein the release time is an earliest time at which the event is intended to be delivered to the client;

obtaining a completion time, wherein the completion time is a latest time at which the event can arrive at the client;

determining a first latency between the trusted edge server and a first client communicating with the first trusted server;

comparing the first latency to a first transfer latency;

transferring the first client if the first transfer latency is lower than the first latency;

calculating a first send time as a function of the first latency and the first transfer latency; and

sending the event to the first client at the first send time, wherein the first transfer latency is a latency between a second trusted edger server and the first client and wherein transferring the first client if the first transfer latency is lower than the first latency includes transferring the first client to the second trusted edger server.

25. The computer-readable medium of claim 24, having further computer-executable instructions for distributing the event from a second trusted edge server to a second client, wherein calculating the first send time as a function of the first latency and the first transfer latency includes calculating the first send time as a function of a second latency and a second transfer latency, the further computer-executable instructions performing steps comprising:

determining the second latency between a second trusted edge server and a second client;

comparing the second latency to a second transfer latency;

transferring the second client if the second transfer latency is lower than the second latency; and

sending the event to the second client at the first send time.

26. The computer-readable medium of claim 24, wherein the event is distributed from a second trusted edge server to a second client, the second client having a second latency, the computer-executable instructions performing steps further comprising:

comparing the second latency to a second transfer latency;

transferring the second client if the second transfer latency is lower than the second latency;

calculating a second send time as a function of the second latency and the second transfer latency; and

sending the event to the second client at the second send time.

27. A system for network distribution to minimize latencies, the system comprising:

an originating server;

a first trusted edge server having connected to it a client;

a second trusted edge server, wherein a trusted edge server is a server, in a communications path between the originating server and a connected client, that can be trusted not to release information prior to an appropriate time; and

computer-executable instructions for performing steps comprising;

determining a first latency between the first trusted edge server and the client;

determining a second latency between the second trusted edge server and the client;

comparing the first latency to the second latency; and

transferring the client to the second trusted edge server if the second latency is lower than the first latency, wherein the computer-executable instructions perform further steps comprising;

obtaining a release time, wherein the release time is an earliest time at which an event is intended to be delivered to the client;

obtaining a completion time, wherein the completion time is a latest time at which the event can arrive at the client;

calculating a send time as a function of the first latency and the second latency; and

sending the event to the client at the send time.

28. A system for efficient distribution, the system comprising:

an originating server;

a trusted edger server having connected to it a first client, wherein the trusted edge server is a server, in a communications path between the originating server and a connected client, that can be trusted not to release information prior to an appropriate time; and

computer-executable instructions for performing steps comprising;

obtaining a release time, wherein the release time is an earliest time at which the event is intended to be delivered to the first client;

obtaining a completion time, wherein the completion time is a latest time at which the event can arrive at the first client;

determining a first latency between the trusted edge server and the first client;

calculating a first send time as a function of the first latency; and

sending the event from the trusted edge server to the client at the first send time, wherein the step of calculating the first send time further comprises;

estimating a first delivery time using the first latency; and

calculating the first send time to be prior to the completion time minus the first delivery time.

29. The system of claim 28, wherein the step of calculating the first send time as a function of the first latency includes calculating the first send time as a function of a second latency, the system further comprising:

computer-executable instructions for performing steps comprising;

sending the event from the trusted edge server to a second client, the second client having a second latency, at the first send time.

30. The system of claim 29 wherein the step of calculating the first send time further comprises:

estimating a first delivery time as a function of the first latency;

estimating a second delivery time as a function of the second latency;

calculating the first send time to be prior to the completion time minus the first delivery time if the first delivery time is greater than the second delivery time; and

calculating the first send time to be prior to the completion time minus the second delivery time if the second delivery time is greater than the first delivery time.

31. The system of claim 28, further comprising:

computer-executable instructions for performing steps comprising;

determining a second latency between the trusted edge server and a second client;

calculating a second send time as a function of the second latency; and

sending the event from the trusted edge server to the second client at the second send time.

32. The system of claim 31, further comprising:

computer-executable instructions for performing steps comprising;

determining an originating latency between the originating server and the trusted edge server;

calculating an originating send time as a function of the first send time, the second send time, and the originating latency; and

sending the event from the originating server to the trusted edge server at the originating send time.

33. The system of claim 28, further comprising:

computer-executable instructions for performing steps comprising;

determining an originating latency between the originating server and the trusted edge server;

calculating an originating send time as a function of the first send time and the originating latency; and

sending the event from the originating server to the trusted edge server at the originating send time.

34. The system of claim 28, wherein:

the computer-executable instructions for determining the first latency include computer-executable instructions for performing steps comprising;

determining a transfer latency;

comparing the first latency to a transfer latency; and

transferring the first client to a second trusted edge server if the transfer latency is lower than the first latency;

the computer-executable instructions for calculating the first send time include computer-executable instructions for determining the first send time as a function of a second latency between the second trusted edge server and the first client; and

the computer-executable instructions for sending the event include computer-executable instructions for sending the event from the second trusted edge server to the first client at the first send time if the transfer latency is lower than the first latency.

35. The system of claim 34, wherein the transfer latency is a latency between the second trusted edge server and the first client.

36. The system of claim 34, wherein the transfer latency is a minimum theoretical latency.

37. A system for efficient event distribution, the system comprising:

a first trusted edge server having connected to it a first client;

a second trusted edger server, wherein a trusted edge server is a server, in a communications path between an originating server and a connected client, that can be trusted not to release information prior to an appropriate time; and

computer-executable instructions for performing steps comprising;

obtaining a release time, wherein the release time is an earliest time at which the event is intended to be delivered to the first client;

obtaining a completion time, wherein the completion time is a latest time at which the event can arrive at the first client;

determining a first latency between the trusted edge server and the first client;

comparing the first latency to a first transfer latency;

transferring the first client if the first transfer latency is lower than the first latency;

calculating a first send time as a function of the first latency and the first transfer latency; and

sending the event to the first client at the first send time, wherein the first transfer latency is a latency between the second trusted edger server and the first client and wherein the computer-executable instructions for transferring the first client if the first transfer latency is lower than the first latency include computer-executable instructions for transferring the first client to the second trusted edger server.

38. The system of claim 37, wherein the computer-executable instructions for calculating the first send time as a function of the first latency and the first transfer latency include computer-executable instructions for calculating the first send time as a function of a second latency and a second transfer latency, the system further comprising:

computer-executable instructions for performing steps comprising;

determining the second latency between the second trusted edge server and a second client;

comparing the second latency to the second transfer latency;

transferring the second client if the second transfer latency is lower than the second latency; and

sending the event to the second client at the first send time.

39. The system of claim 38, wherein the second trusted edge server is the first trusted edge server.

40. The system of claim 38, wherein the computer-executable instructions for calculating the first send time further comprise computer-executable instructions for performing steps comprising:

estimating a first delivery time as a function of the first latency and the first transfer latency;

estimating a second delivery time as a function of the second latency and the second transfer latency;

calculating the first send time to be prior to the completion time minus the first delivery time if the first delivery time is greater than the second delivery time; and

calculating the second send time to be prior to the completion time minus the second delivery time if the second delivery time is greater than the first delivery time.

41. The system of claim 37, further comprising:

computer-executable instructions for performing steps comprising;

determining a second latency between the second trusted edge server and a second client;

comparing the second latency to a second transfer latency;

transferring the second client if the second transfer latency is lower than the second latency;

calculating a second send time as a function of the second latency and the second transfer latency; and

sending the event to the second client at the second send time.

42. A method of distributing an event from a trusted edge server to a client, wherein the trusted edge server is a server, in a communications path between an originating server and a connected client, that can be trusted not to release information prior to an appropriate time, the method comprising:

a step for obtaining a release time, wherein the release time is an earliest time at which the event is intended to be delivered to the client;

a step for obtaining a completion time, wherein the completion time is a latest time at which the event can arrive at the client;

a step for determining a first latency between the trusted edge server and a first client;

a step for calculating a first send time as a function of the first latency; and

a step for sending the event from the trusted edge server to the client at the first send time, wherein the step for calculating the first send time further comprises;

a step for estimating a first delivery time using the first latency; and

a step for calculating the first send time to be prior to the completion time minus the first delivery time.

43. The method of claim 42 further comprising:

a step for determining a second latency between the trusted edge server and a second client;

a step for calculating a second send time as a function of the second latency; and

a step for sending the event from the trusted edge server to the second client at the second send time.

44. The method of claim 42, wherein:

the step for determining the first latency includes;

a step for determining a transfer latency;

a step for comparing the first latency to the transfer latency; and

a step for transferring the first client to a second trusted edge server if the transfer latency is lower than the first latency;

the step for calculating the first send time includes a step for determining the first send time as a function of a second latency between the second trusted edge server and the first client; and

the step for sending the event includes a step for sending the event from the second trusted edge server to the first client at the first send time if the transfer latency is lower than the first latency.

45. A trusted edge server for distributing an event to a client, wherein the trusted edge server is a server, in a communications path between an originating server and a connected client, that can be trusted not to release information prior to an appropriate time, comprising:

means for obtaining a release time and a completion time, wherein the release time is an earliest time at which the event is intended to be delivered to the client, and the completion time is a latest time at which the event can arrive at the client;

means for determining a first latency between the trusted edge server and a first client;

means for calculating a first send time as a function of the first latency; and

means for sending the event from the trusted edge server to the client at the first send time, wherein means for calculating the first send time further comprises;

means for estimating a first delivery time using the first latency; and

means for calculating the first send time to be prior to the completion time minus the first delivery time.

46. The trusted edge server of claim 45, wherein the means for calculating the first send time as a function of the first latency include means for calculating the first send time as a function of a second latency between the trusted edge server and a second client, and wherein the means for sending the event from the trusted edge server to the first client at the first send time include means for sending the event from the trusted edge server to the second client at the first send time.

47. The trusted edge server of claim 46, wherein the means for calculating the first send time further comprise:

means for estimating a first delivery time as a function of the first latency, and a second delivery time as a function of the second latency;

means for calculating the first send time to be prior to the completion time minus the first delivery time if the first delivery time is greater than the second delivery time; and

means for calculating the first send time to be prior to the completion time minus the second delivery time if the second delivery time is greater than the first delivery time.

48. A trusted edge server for distributing an event to a client, wherein the trusted edge server is a server, in a communications path between an originating server and a connected client, that can be trusted not to release information prior to an appropriate time, comprising:

means for obtaining a release time and a completion time, wherein the release time is an earliest time at which the event is intended to be delivered to the client, and the completion time is a latest time at which the event can arrive at the client;

means for determining a first latency between the trusted edge server and a first client communicating with the first trusted server;

means for comparing the first latency to a first transfer latency;

means for transferring the first client if the first transfer latency is lower than the first latency;

means for calculating a first send time as a function of the first latency and the first transfer latency; and

means for sending the event to the first client at the first send time, wherein the first transfer latency is a latency between a second trusted edger server and the first client and wherein means for transferring the first client if the first transfer latency is lower than the first latency includes means for transferring the first client to the second trusted edger server.