Continuous media file server system and method for scheduling network resources to play multiple files having different data transmission rates

• US 6,134,596 A
• Filed: 09/18/1997
• Issued: 10/17/2000
• Est. Priority Date: 09/18/1997
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Bolosky, William J., Douceur, John R.
• Primary Examiner(s): Luu, Le Hien
• Application Number:
  US08/934,972
• Time in Patent Office: 1,125 Days
• Field of Search: 709/232, 709/104, 709/233, 709/213, 455/4.2, 370/394, 348/7, 345/327, 710/21, 714/1
• US Class Current: 709/233
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 65/1101 Session protocols
• CPC Class Codes: H04L 65/612 for unicast
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• CPC Class Codes: H04L 67/62 Establishing a time schedule for servicing the requests
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols
• CPC Class Codes: H04N 21/21 Server components or server architectures
• CPC Class Codes: H04N 21/23 Processing of content or additional data; Elementary server operations; Server middleware

Abstract

A continuous media file server system has a controller connected to multiple data servers. Each data server supports at least one storage disk. Data files are distributed across the data servers so that data blocks of the data files are stored on each of the storage disks. The data files have different data transmission rates at which they are served over a network to clients in the form of data streams. A scheduling unit maintains a network schedule that provides a relative ordering of transmission times of requested data streams. The transmission times indicate when the data servers are to transmit corresponding data blocks of the requested data files over the network to stream the data to clients. The block play times for all data files have a fixed duration, with the size of the data blocks from data file to data file varying according to the data transmission rates of the files. When a transmission time for a data file block approaches, the scheduling unit instructs the appropriate data server to read a data block for that data file from the disk prior to the transmission time in the network schedule. In this manner, disk reads are scheduled implicitly according to the network schedule. The data is temporarily stored in buffer memory, and later transmitted over the network. When a request for a new data stream is received, the scheduling unit evaluates whether the new data stream can be inserted into the network schedule without overburdening the data servers'"'"' ability to serve the existing data streams on the network schedule.

Claims

1. In a continuous media file server system having multiple data servers connected to distribute data streams over a network, each data server supporting at least one storage disk, wherein data files are distributed across the data servers and stored on each of the storage disks, and wherein not all of the data files have the same transmission rate, a method comprising the following steps:

scheduling when the data servers are to transmit segments of a first size of a first requested data file over the network and when the data servers are to transmit segments of a second size of a second requested data file over the network based on a network schedule arranged to maximize network bandwidth utilization, and wherein the first size is different from the second size;

reading the segments from the disks associated with the data servers prior to when the data servers are scheduled to transmit the segments, and

separately, completely transmitting the segments of the first size and the segments of the second size during corresponding transmission times over single communication channels, wherein the transmission times are of equal fixed durations.

2. A method as recited in claim 1, wherein the scheduling step comprises the step of establishing the network schedule that orders a transmission time for the requested data file, the transmission time specifying when the data servers are to transmit the segments of the first and second requested data files over the network.

3. A method as recited in claim 1, wherein the scheduling step comprises the step of scheduling when the data servers are to transmit redundant copies of the segments the first and second requested data files over the network in an event of a failure.

4. A method as recited in claim 1, wherein the scheduling step is performed at each of the data servers.

5. A method as recited in claim 1, wherein the file server system further comprises a controller connected to each of the data servers, and the scheduling step is performed at the controller.

6. A method as recited in claim 1, wherein the reading step further comprises the steps of:

reading the segments of the first and second requested data files from the disks at an earliest possible time prior to when the data servers are scheduled to transmit the segments; and

storing the segments of the first and second requested data files at the data servers.

7. A method as recited in claim 1, wherein the reading step further comprises the following steps:

reading the segments of the first and second requested data files from the disks at an earliest possible time prior to when the data servers are scheduled to transmit the segments, yet without exceeding a preset maximum lead time before the schedule transmission; and

storing the segments of the first and second requested data files at the data servers.

8. A method as recited in claim 1, wherein the reading step further comprises the step of reading the segments of the first and second requested data files from the disks at a latest possible time prior to when the data servers are scheduled to transmit the segments.

9. In a continuous media file server system having multiple data servers connected to distribute data streams over a network, each data server supporting at least one storage disk, wherein data files are distributed across the data servers and stored on each of the storage disks, and wherein not all of the data files have the same transmission rate, a method comprising the following steps:

scheduling transmission times of multiple data files of different data transmission rates into a network schedule to maximize network bandwidth utilization, the transmission times within the network schedule indicating a relative order in which the data servers are to transmit corresponding blocks of the data files over the network, and wherein the corresponding blocks of at least two of the data files are different in size;

reading the blocks from the disks associated with the data servers prior the transmission times in the network schedule; and

separately, completely transmitting the blocks of the data files over single communication channels in the network during corresponding transmission times, wherein the transmission times are of equal fixed durations.

10. A method as recited in claim 9, wherein the scheduling step comprises the step of scheduling secondary transmission times into the network schedule, the secondary transmission times indicating a relative order in which the data servers are to transmit redundant copies of the blocks in an event of failure.

11. A method as recited in claim 9, further comprising the following steps:

distributing portions of the network schedule among the data servers; and

at each of the data servers, transmitting the blocks for the data files that have transmission times listed on the portions of the network schedule presently held by the data servers.

12. A method as recited in claim 11, further comprising the step of circulating respective portions of the network schedule among the data servers to maintain scheduled distribution of the data files.

13. A method as recited in claim 9, wherein the file server system further comprises a controller connected to each of the data servers, and the scheduling step is performed at the controller.

14. A method as recited in claim 9, wherein the network schedule orders the transmission times so that the multiple data streams can be concurrently served without overburdening resources of the file server system.

15. A method as recited in claim 9, wherein the reading step comprises the step of reading the blocks from the disks at an earliest possible time prior to the transmission times.

16. A method as recited in claim 9, wherein the reading step comprises the step of reading the blocks from the disks at an earliest possible time prior to the transmission times without exceeding a preset maximum lead time.

17. A method as recited in claim 9, wherein the reading step comprises the step of reading the blocks from the disks at a latest possible time prior to the transmission times.

18. A method as recited in claim 9, wherein the reading step comprises the step of reading the blocks from the disks at a latest possible time prior to the transmission times and in the event that blocks from two different data streams are to be read concurrently, reading the blocks associated with the data stream with the sooner transmission time first.

19. A method as recited in claim 9, further comprising the step of searching the network schedule for a suitable position to add a new data stream whereby the position in the network schedule does not overload the file server system when serving the existing data stream at their various data transmission rates and the new data stream.

20. A method as recited in claim 19, wherein the network schedule is a linked-list data structure, and the searching step comprises the step of linearly searching the network schedule.

21. A method as recited in claim 19, wherein the network schedule is a linked-list data structure, and the searching step comprises the step of traversing a search tree representative of the network schedule.

22. In a continuous media file server system having multiple data servers connected to distribute data streams over a network, each data server supporting at least one storage disk, wherein data flies are distributed across the data servers and stored on each of the storage disks, and wherein not all of the data files have the same transmission rate, a method comprising the following steps:

scheduling transmission times of multiple data streams of different data transmission rates into a network schedule to maximize network bandwidth utilization, the transmission times indicating a relative order in which the data servers are to transmit corresponding blocks of the data files over the network, and wherein the corresponding blocks of at least two of the data streams are different in size;

in an event that a new data stream is requested, searching the network schedule for a suitable position to add the new data stream without overloading resources of the file server system; and

separately, completely transmitting the blocks of the data files over single communication channels in the network during corresponding transmission times, wherein the transmission times are of equal fixed durations.

23. A method as recited in claim 22, wherein the network schedule is a linked-list data structure, and the searching step comprises the step of linearly searching the network schedule.

24. A method as recited in claim 22, wherein the network schedule is a linked-list data structure, and the searching step comprises the step of traversing a search tree representative of the network schedule.

25. A method as recited in claim 22, wherein the data servers have buffer memory to temporarily store data read from the disks prior to transmission over the network, the method further comprising the step of examining whether a data block from a new data file, if the new data file is read at a particular location in the network schedule, would cause the buffer memory capacity to be exceeded.

26. A method as recited in claim 22, further comprising the step of adding the new data stream to the network schedule if the suitable position is found.

27. A method for operating a data server in a continuous media file server system having multiple data servers connected to distribute data streams over a network, each data server supporting at least one storage disk, wherein data files are distributed across the data servers and stored on each of the storage disks, and wherein not all of the data files have the same transmission rate, the method comprising the following steps:

receiving a portion of a network schedule from a preceding data server, the network schedule containing transmission times of one or more data streams of one or more data transmission rates wherein the transmission times indicate a relative order in which the data streams are to be played to maximize network bandwidth utilization;

reading data blocks from the data files that have corresponding transmission times on the portion of the network schedule, said reading step occurring prior to the transmission times; and

transmitting the data blocks over single communication channels during the transmission times in the portion of the network schedule, and wherein the data blocks of at least two of the data files are different in size, and each of the transmission times is of an equal fixed duration.

28. A method as recited in claim 27, further comprising the step of passing the portion of the network schedule to a succeeding data server and receiving a new portion of the network schedule from the preceding data server.

29. A method as recited in claim 27, further comprising the following steps:

storing the data block temporarily in buffer memory; and

evaluating whether reading another data block, in an event that a new transmission time for a new data file is added to the portion of the network schedule, would cause the buffer memory capacity to be exceeded.

30. A method as recited in claim 29, further comprising the step of tentatively inserting the new transmission time into the portion of the network schedule if reading said another data block does not cause the buffer memory capacity to be exceeded.

31. A method as recited in claim 29, further comprising the step of sending a message to at least one succeeding data server requesting the succeeding data server to confirm whether it can accommodate the new data file in the succeeding data server'"'"'s portion of the network schedule.

32. A continuous media file server system, comprising:

multiple data servers, each data server supporting at least one storage disk, wherein data files are distributed across the data servers so that data blocks of the data files are stored on each of the storage disks, and not all of the data files have the same transmission rate and therefore the corresponding data blocks of at least two of the data files are different in size;

a controller coupled to the data servers;

a network switch coupled to the data servers;

a scheduler to maintain a network schedule that provides a relative ordering of transmission ties of requested data files, the transmission times indicating when the data servers are to transmit corresponding data blocks of the requested data files over the network switch to maximize network bandwidth utilization; and

the data servers reading the data blocks from the disks prior to the transmission times in the network schedule, and wherein each of the transmission times is of an equal fixed duration and associated with transmitting the data blocks over single communication channels.

33. A continuous media file server system as recited in claim 32, wherein the scheduler resides at the controller and maintains a master network schedule.

34. A continuous media file server system as recited in claim 32, wherein the scheduler resides at each of the data servers and maintains portions of the network schedule pertinent to each of the data servers.

35. A continuous media file server system as recited in claim 32, wherein the blocks are transmitted for a constant duration and the data blocks are variable in size.

36. A continuous media file server system as recited in claim 32, wherein the data servers read the data blocks from the disks at an earliest possible time prior to the transmission times.

37. A continuous media file server system as recited in claim 32, wherein the data servers read the data blocks from the disks at an earliest possible time prior to the transmission times without exceeding a preset maximum lead time.

38. A continuous media file server system as recited in claim 32, wherein the data servers read the data blocks from the disks at a latest possible time prior to the transmission times.

39. A continuous media file server system as recited in claim 32, wherein the data servers read the data blocks from the disks at a latest possible time prior to the transmission times and in an event that blocks from two different data streams are to be read concurrently, the data servers read the blocks associated with the data stream with the sooner transmission time.

40. A continuous media file server system as recited in claim 32, wherein the scheduling unit evaluates the network schedule to determine whether a new data file can be added without overburdening the data servers.

41. An interactive television system comprising the continuous media file server system as recited in claim 32.

42. A network content provider comprising the continuous media file server system as recited in claim 32.

43. A network scheduler embodied as a computer program on a computer-readable medium, the network scheduler being implemented in a continuous media file server system having multiple data servers connected to distribute data streams over a network, each data server supporting at least one storage disk, wherein data files are distributed across the data servers and stored on each of the storage disks, and not all of the data files have the same transmission rate, the network scheduler comprising:

code means for scheduling transmission times of multiple requested data files of different data transmission rates into a network schedule, the transmission times within the network schedule indicating a relative order in which the data servers are to transmit corresponding blocks of the data files over the network to maximize network bandwidth utilization; and

code means for instructing the data servers to read the blocks for the requested data files prior their corresponding transmission times in the network schedule, and wherein the blocks of at least two of the data files are different in size, and each of the transmission times is of an equal fixed duration and associated with transmitting the blocks over single communication channels.

44. A network scheduler as recited in claim 43, further comprising code means for determining whether a new data stream can be added to the network schedule.

45. A network scheduler as recited in claim 43, further comprising code means for scheduling secondary transmission times into the network schedule, the secondary transmission times indicating a relative order in which the data servers are to transmit redundant copies of the blocks in an event of failure.

46. A network scheduler as recited in claim 43, wherein the network schedule is a linked-list data structure.

47. A network scheduler as recited in claim 43, wherein the data servers have buffer memory to temporarily store data read from the disks prior to transmission, the network scheduler further comprising code means for examining whether a data block from the new data file, if the new data file is read at a particular location in the network schedule, would cause the buffer memory capacity to be exceeded.

48. A network scheduler embodied as a computer program on a computer-readable medium resident at a data server, the data server being part of a continuous media file server system having multiple data servers connected to distribute data streams over a network, each of the data servers supporting at least one storage disk, wherein data files are distributed across the data servers and stored on each of the storage disks, and wherein not all of the data files have the same transmission, rate, the network scheduler comprising:

code means for receiving a portion of a network schedule from a preceding data server, the network schedule containing transmission times of one or more data files of one or more data transmission rates wherein the transmission times indicate a relative order in which the data files are to be played to maximize network bandwidth utilization;

code means for instructing the data server to read a data block from the data files that have corresponding transmission times on the portion of the network schedule, prior to the transmission times; and

code means for instructing the data server to transmit the data blocks during the transmission times in the portion of the network schedule, and wherein the corresponding blocks of at least two of the data files are different in size, and each of the transmission times is of an equal fixed duration and associated with transmitting the data blocks over single communication channels.

49. A network scheduler as recited in claim 48, further comprising:

code means for determining whether a new data stream can be inserted into the portion of the network schedule; and

code means for sending a message to at least one succeeding data server requesting whether the succeeding data server can accommodate the new data stream in a portion of the network schedule held by the succeeding data server.