Electrical computers and digital processing systems: multicomput – Computer-to-computer protocol implementing – Computer-to-computer data streaming
Reexamination Certificate
1999-03-10
2002-06-04
Wiley, David (Department: 2155)
Electrical computers and digital processing systems: multicomput
Computer-to-computer protocol implementing
Computer-to-computer data streaming
C709S202000, C709S231000, C709S232000, C709S233000, C709S226000, C709S243000, C370S395430, C370S397000, C370S230000, C370S473000, C710S006000, C345S215000, C725S115000, C707S793000, C711S118000
Reexamination Certificate
active
06401126
ABSTRACT:
TECHNICAL FIELD
This invention relates to continuous media file server systems that simultaneously serve multiple data streams to a large number of clients. More particularly, this invention relates to methods for scheduling service of data streams in a distributed schedule maintained throughout a file server system in a manner that minimizes clustering of scheduled data streams within the distributed schedule and maximizes gaps in the schedule between scheduled data streams.
BACKGROUND
A continuous media file server system is designed to serve continuous data streams, such as audio and video data files, to multiple clients. As an example, a file server system might simultaneously supply multiple digital data streams, each in the 1-10 megabits-per-second (Mb/s) range, to thousands of clients.
General Architecture
FIG. 1
shows a continuous media file server system
20
developed by Microsoft Corporation. The file server system is a distributed, scalable, and fault-tolerant server that can serve many continuous data streams simultaneously to a large number of clients. The file server system
20
has a central controller
22
connected to multiple data servers
24
(
1
),
24
(
2
),
24
(
3
), . . . ,
24
(K) via a low bandwidth control network
26
. The controller
22
receives requests from clients, such as requests for starting and stopping a particular data file. The controller
22
is responsible for initiating delivery of streaming content to the requesting clients, including such tasks as locating the data server that holds the first block of data in the requested data file. The controller and data servers can be implemented, for example, as general purpose computers.
Each data server
24
supports at least one storage device, such as a disk, as represented by storage disks
28
(
1
),
28
(
2
), . . . ,
28
(M) connected to data server
24
(
1
). The disks
28
are attached to their respective data server
24
via one or more buses
30
(e.g., SCSI, Fiber Channel, EIDE, etc.). The number and configuration of storage disks are flexible, but within a given file server
20
, all data servers
24
support the same number of storage disks
28
. The storage disks can store large amounts of digital data, with example disk capacities of many Gigabytes. The storage capacity of the entire media file server
20
consists of the usable storage space on the storage disks. An operator can change the storage capacity of the file server by adding or removing one or more storage disks to or from each data server, or adding or removing one or more of the data servers to which the disks are connected.
The data servers
24
are connected to a high-speed network switch
32
via network interfaces
34
(e.g., network card). The network switch
32
takes the data segments read from the storage disks, orders them into a continuous stream, and distributes the streams over a network to the clients. The network switch
32
also provides high bandwidth, parallel communication between the data servers
24
. Additionally, the controller
22
may be connected to the data servers
24
through the network switch
32
, as opposed to a separate control network
26
. As an example, the network switch
32
can be implemented using fiber optics and ATM (Asynchronous Transfer Mode) switches.
Each data server
24
contains a memory buffer, as represented by buffer
36
in data server
24
(
1
). The buffer
36
temporarily stores data that is read from the disks
28
(
1
)-
28
(M) and is to be output to the network switch
32
.
The continuous media file server system
20
can be implemented in different contexts. For instance, the file server system
20
might function as a head end server in an interactive television (ITV) system, which serves audio and video files over a distribution network (e.g., cable, satellite, fiber optic, etc.) to subscriber homes. The file server system
20
might alternatively operate as a content provider that distributes data files over a network (e.g., Internet, LAN, etc.) to multiple client computers.
Data Striping
It is likely that some pieces of content will be more popular than others. For example, the top ten percent of movies ordered by popularity might garner 70% of the load, while the remaining 90% of the content attracts only 30% of the viewers. To avoid disproportionate use of storage disks
28
and data servers
24
(i.e., by overburdening the disks and data servers holding popular content while leaving other disk and data servers underutilized), the continuous media file server system
20
stripes all of the data files across all of the storage disks
28
and all of the data servers
24
. When a client requests a data stream, all data servers
24
share in the distribution of that stream, each supplying a portion of the data stream in turn. In this way, the load is spread over all of the storage disks
28
and data servers
24
regardless of the data file's popularity.
Prior to this invention, the data streams were served at a constant data transmission bit rate. With this assumption, each data file could be broken into “blocks” of fixed temporal width. A block represented the amount of physical space allocated on a disk to hold one time unit of data, and could be expressed in terms of bytes. The temporal duration required to play the data in the block is known as a “block play time”. For a data rate of 1 Mb/s, for example, the block size might be 1 Megabit and the block play time might be one second. In the conventional file server, a single block play time is established for all data files, resulting in a fixed-size data block.
FIG. 2
shows an example file server disk array
40
consisting of six data servers
0
-
5
, each supporting two storage disks. Each disk stores data blocks, as represented by the labeled rectangles such as “A
0
”, “A
6
”, etc. Data files are striped across every storage disk of every server. For each data file, a starting disk is chosen to hold the first data block. For instance, the first block of data file A, designated as block “A
0
”, is stored on disk
0
of data server
0
. A server index is incremented, and the next block in the file (i.e., block “A
1
”) is placed on disk
0
of server
1
. The striping continues across the first disks of each server.
When the last server
5
is reached, the striping pattern wraps and continues with the next disks of each server. More specifically, when the server index reaches the number of servers in the system, a disk index is incremented (modulo the number of disks per server) and the server index is reset to 0. In
FIG. 2
, after data block A
5
is placed on disk
0
of server
5
, the next block in the file (i.e., block “A
6
”) is placed on disk
1
of server
0
. Block A
7
is then placed on disk
1
of server
1
, and so on. This process continues until all the data blocks of the video file have been assigned to disks.
The process is then repeated for each subsequent data file. Typically, the striping pattern starts the various data files on different starting disks. In
FIG. 2
, two data files A and B are shown. Data file A begins on disk
0
of server
0
, and data file B begins on disk
0
of server
1
.
The striping pattern generally prescribes that the data blocks are sequentially ordered across ordered disks, but the sequential blocks need not reside at the same physical block address on adjacent disks. For instance, the striping pattern of files A and B result in the storage of sequential blocks B
3
(disk
0
, server
4
) and B
4
(disk
0
, server
5
) at different physical locations on the two disks (location
3
for block B
3
and location
2
for block B
4
). Accordingly, sequential data blocks can reside at entirely different physical block locations within the contiguous disks. The block locations in the disk array are described by file metadata that is stored either in memory or on disk. It is noted that other patterns are possible.
To play a data file, the file server system
20
serves the data blocks sequentially from the storage disks, one block at a time. The data blocks
Bolosky William J.
Douceur John R.
Duong Oanh L.
Lee & Hayes PLLC
Microsoft Corporation
Wiley David
LandOfFree
File server system and method for scheduling data streams... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with File server system and method for scheduling data streams..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and File server system and method for scheduling data streams... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2895097