Packet scheduling system and method for multimedia data
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
24 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
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. - View Dependent Claims (10, 11, 12, 13)
-
-
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. - View Dependent Claims (15, 16, 17)
-
-
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. - View Dependent Claims (19, 20, 21, 22)
-
-
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.
-
Specification