Packet scheduling system and method for multimedia data

• US 6,988,144 B1
• Filed: 09/18/2000
• Issued: 01/17/2006
• Est. Priority Date: 11/18/1999
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Wood, Stephen P., Luken, William L.
• Primary Examiner(s): Maung, Zarni
• Assistant Examiner(s): DINH, KHANH Q
• Application Number:
  US09/663,490
• Time in Patent Office: 1,947 Days
• Field of Search: 709/224, 709/236, 709/231, 709/105, 709/220, 709/225, 709/226, 709/228, 709/232, 709/203, 370/477, 370/510, 370/229, 370/230, 370/233, 370/235, 370/253, 370/395.42, 370/236, 475/240, 375/225, 375/240
• US Class Current: 709/231
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/22 Traffic shaping
• CPC Class Codes: H04L 47/2416 Real-time traffic
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/564 Attaching a deadline to packets, e.g. earliest due date first
• CPC Class Codes: H04L 47/626 channel conditions
• CPC Class Codes: H04L 49/90 Buffering arrangements

Abstract

A method for scheduling the delivery of multimedia data packets over a communications medium with a limited bandwidth. The packets may contain data representing images, sounds, or other media which are to be delivered from a source or server to a recipient or client. The 6 method described here minimizes the delay between the point in time when a client requests the multimedia data and the point in time when the client may start presenting the data without risk of interruption, for a given communications bandwidth. This method also determines the minimum buffer sizes needed by the client in order to present this multimedia data subject to the specified bandwidth limit.

Claims

1. A method for scheduling the delivery of data packets representing one or more media data tracks, said method allowing the data packets to be delivered from a server to a client with a given bandwidth so as to minimize the initial delay required for the client to present the data without interruption, said method including the steps of:

creating a list of virtual data packets representative of all data packets to be scheduled for delivery from the server to the client;

calculating a delivery deadline for each virtual data packet based on the communications bandwidth from the server to the client and a point in time at which the client must act on the data, wherein the delivery deadline for each virtual data packet is calculated as

t(deadline)=t(start)−

(packetsize)/bandwidth)

where t(start) is the point in time when the client needs to act on the data contained in the packet, (packetsize) is the number of bytes in the corresponding data packet, and (bandwidth) is the communications bandwidth from the server to the client in bytes per second;

sorting the list of virtual data packets based on the delivery deadlines calculated for each virtual data packet, to provide a sorted list; and

delivering the data packets in accordance with the sorted list.

2. The method claim 1 further comprising:

resolving temporal collisions between virtual data packets.

3. The method of claim 2, wherein the step of resolving temporal collisions is accomplished by comparing each virtual data packet in the sorted list of virtual data packets to the preceding member of this list, starting with the member of this list having the latest delivery deadline and ending with the member of this list having the earliest delivery deadline.

4. The method of claim 1, said method including an additional step for removing temporal gaps between successive virtual data packets.

5. The method of claim 4, wherein the step of removing temporal gaps is accomplished by comparing each virtual data packet in the sorted list of virtual data packets to the next successive member of this list, starting with a first member of the list having the earliest delivery deadline and ending with a last member of this list having the latest delivery deadline.

6. The method of claim 1 further comprising the steps of:

determining optimal client buffer size based on the communications bandwidth; and

communicating optimal client buffer size information to the client.

7. The method of claim 1 wherein the communications bandwidth varies, further comprising the steps of:

determining a new communications bandwidth;

calculating a revised sorted list based on the new communications bandwidth;

replacing the sorted list with the revised sorted list; and

continuing delivery of packets according to the revised sorted list.

8. The method of claim 7 further comprising the steps of:

determining optimal client buffer size based on the new communications bandwidth; and

communicating the optimal client buffer size to the client.

9. A method for interleaving the data packets representing two or more media data tracks, said method allowing the data packets to be delivered from a server to a client with a given bandwidth so as to minimize the initial delay required for the client to present the data without interruption, said method including the steps of:

creating a list of virtual data packets representative of all data packets to be scheduled for delivery from the server to the client;

calculating delivery deadlines for each virtual data packet based on the communications bandwidth from the server to the client and a point in time at which the client must act on the data, wherein the delivery deadline for each virtual data packet is calculated as

t(deadline)=t(start)−

(packetsize)/(bandwidth)

where t(start) is the point in time when the client needs to act on the data contained in the packet, (packetsize) is the number of bytes in the corresponding data packet, and (bandwidth) is the communications bandwidth from the server to the client in bytes per second;

sorting the list of virtual data packets into a sorted list based on the delivery deadlines calculated for each virtual data packet; and

delivering non-sequential data packets based on said sorted list.

10. The method of claim 9 further comprising:

resolving temporal collisions between virtual data packets.

11. The method of claim 10, wherein the step of resolving temporal collisions is accomplished by comparing each virtual data packet in the sorted list of virtual data packets to the preceding member of this list, starting with the last member of this list having the latest delivery deadline and ending with the first member of this list having the earliest delivery deadline.

12. The method of claim 9, said method including an additional step for removing temporal gaps between successive virtual data packets.

13. The method of claim 12, wherein the step of removing temporal gaps is accomplished by comparing each virtual data packet in the sorted list of virtual data packets to the next successive member of this list, starting with the first member of this list having the earliest delivery deadline and ending with the last member of this list having the latest delivery deadline.

14. A method for determining the minimal initial delay required to deliver a sequence of data packets representing one or more media data tracks from a server to a client without interruption for a given bandwidth, said method including the steps of:

creating a list of virtual data packets representative of all data packets to be scheduled for delivery from the server to the client;

calculating delivery deadlines for each virtual data packet based on the communications bandwidth from the server to the client and a point in time at which the client must act on the data, wherein the delivery deadline for each virtual data packet is calculated as

t(deadline)=t(start)−

(packetsize)/(bandwidth)

where t(start) is the point in time when the client needs to act on the data contained in the packet, (packetsize) is the number of bytes in the corresponding data packet, and (bandwidth) is the communications bandwidth from the server to the client in bytes per second;

sorting the list of virtual data packets based on the delivery deadlines calculated for each virtual data packet into a sorted list; and

calculating the initial delay based on the size of the first data packet on said sorted list.

15. The method of claim 14 further comprising:

resolving temporal collisions between virtual data packets.

16. The method of claim 15, wherein the step of resolving temporal collisions is accomplished by comparing each virtual data packet in the sorted list of virtual data packets to the preceding member of this list, starting with the last member of this list having the latest delivery deadline and ending with the first member of this list having the earliest delivery deadline.

17. The method of claim 14, wherein the minimum initial delay is determined by −

t (deadline) for the first member of the sorted list of virtual data packets having the earliest delivery deadline.

18. A method for determining the minimum size of each media data buffer required by a client to allow the client to receive a sequence of data packets representing one or more media data tracks from a server without interruption for a given bandwidth, said method including the steps of:

creating a list of virtual data packets representative of all data packets to be scheduled for delivery from the server to the client;

calculating delivery deadlines for each virtual data packet based on the communications bandwidth from the server to the client and a point in time at which the client must act on the data, wherein the delivery deadline for each virtual data packet is calculated as

t(deadline)=t(start)−

(packetsize)/(bandwidth)

where t(start) is the point in time when the client needs to act on the data contained in the packet, (packetsize) is the number of bytes in the corresponding data packet, and (bandwidth) is the communications bandwidth from the server to the client in bytes per second;

sorting the list of virtual data packets based on the delivery deadlines calculated for each virtual data packet into a sorted list; and

determining the maximum amount of data to be stored in the buffer as a function of time based the size of the virtual data packets and the delivery schedule from said sorted list; and

identifying said minimum buffer size based on said maximum amount of data to be stored.

19. The method of claim 18 further comprising:

resolving temporal collisions between virtual data packets.

20. The method of claim 19, wherein the step of resolving temporal collisions is accomplished by comparing each virtual data packet in the sorted list of virtual data packets to the preceding member of this list, starting with the last member of this list having the latest delivery deadline and ending with the first member of this list having the earliest delivery deadline.

21. The method of claim 18, wherein the step of resolving temporal collisions is followed by an additional step for removing temporal gaps between successive virtual data packets.

22. The method of claim 21, wherein the step of removing temporal gaps is accomplished by comparing each virtual data packet in the sorted list of virtual data packets to the following member of this list, starting with the first member of this list having the earliest delivery deadline and ending with the last member of the list having the latest delivery deadline.

23. A server-based system for scheduling the delivery of data packets representing one or more media data tracks and for thereby allowing the data packets to be delivered from the server to a client with a given bandwidth so as to minimize the initial delay required for the client to present the data without interruption, comprising:

at least one media database for storing multimedia data packets;

at least one media delivery component for delivering data packets; and

at least one ordering component for ordering the multimedia data into data packages for delivery, wherein said at least one ordering component comprises;

at least one virtual packet list component for creating a list of virtual data packets representative of all data packets to be scheduled for delivery from the server to the client;

at least one calculating component for calculating a delivery deadline for each virtual data packet based on the communications bandwidth from the server to the client and a point in time at which the client must act on the data, wherein the delivery deadline for each virtual data packet are calculated as

t(deadline)=t(start)−

(packetsize)/(bandwidth)

where t(start) is the point in time when the client needs to act on the data contained in the packet, (packetsize is the number of bytes in the corresponding data packet, and (bandwidth) is the communications bandwidth from the server to the client in bytes per second;

and at least one sorting component for sorting the list of virtual data packets based on the delivery deadlines calculated for each virtual data packet, to provide a sorted list.

24. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for scheduling the delivery of data packets representing one or more media data tracks, said method allowing the data packets to be delivered from a server to a client with a given bandwidth so as to minimize the initial delay required for the client to present the data without interruption, said method including the steps of:

creating a list of virtual data packets representative of all data packets to be scheduled for delivery from the server to the client;

calculating a delivery deadline for each virtual data packet based on the communications bandwidth from the server to the client and a point in time at which the client must act on the data, wherein the delivery deadline for each virtual data packet are calculated as

t(deadline)=t(start)−

(packetsize)/(bandwidth)

where t(start) is the point in time when the client needs to act on the data contained in the packet (packetsize) is the number of bytes in the corresponding data packet, and (bandwidth) is the communications bandwidth from the server to the client in bytes per second; and

sorting the list of virtual data packets based on the delivery deadlines calculated for each virtual data packet, to provide a sorted list.