公开(公告)号：US6154813A

公开(公告)日：2000-11-28

申请号：US996691

申请日：1997-12-23

申请人： Clifford Eric Martin ,  Pudugramam S. Narayanan ,  Banu Ozden ,  Rajeev Rastogi ,  Abraham Silberschatz

发明人： Clifford Eric Martin ,  Pudugramam S. Narayanan ,  Banu Ozden ,  Rajeev Rastogi ,  Abraham Silberschatz

IPC分类号： G06F12/08 ,  G06F12/12

CPC分类号： G06F12/121 ,  G06F12/0866 ,  G06F12/126

摘要： A cache management scheme is disclosed for buffering one or more continuous media files being simultaneously accessed from a continuous media server by a plurality of media clients. The continuous media server stores pages of data that will likely be accessed in a cache or buffer. The continuous media server implements a cache management strategy that exploits the sequential page access patterns for continuous media data, in order to determine the buffer pages to be replaced from the cache. The cache management strategy initially identifies unpinned pages as potential victims for replacement. Each unpinned page is evaluated by the continuous media server and assigned a weight. Generally, the assigned weight ensures that a buffer with a larger weight will be accessed by a client later in time than a buffer with a smaller weight. A page associated with a larger weight will be accessed later and hence, is replaced earlier. A current buffer list is preferably allocated to monitor the buffer pages associated with a given continuous media file. The current buffer list is a data structure pointing to a set of buffer pages in the cache buffer containing the currently buffered pages of the associated continuous media file. Each buffer page in the buffer cache is preferably represented by a buffer header. The current buffer list (CBL) data structure preferably stores, among other things, a pointer to the buffer pages associated with the CBL, identifier information for the CBL and related continuous media file, and information regarding the number of buffered pages associated with the CBL and number of clients currently accessing the associated continuous media file. The buffer header is a data structure containing information describing the state of the corresponding page. The buffer header preferably includes, among other things, a pointer to an actual area of the buffer cache storing a page of data, a number of pointers to create various relationships among the various pages in a CBL, and a fixed count indicating the number many of clients currently accessing the corresponding page of the continuous media file.

公开(公告)号：US5721956A

公开(公告)日：1998-02-24

申请号：US440737

申请日：1995-05-15

申请人： Clifford Eric Martin ,  Banu Ozden ,  Rajeev Rastogi ,  Abraham Silberschatz

发明人： Clifford Eric Martin ,  Banu Ozden ,  Rajeev Rastogi ,  Abraham Silberschatz

IPC分类号： G06F3/06 ,  H04N7/173 ,  H04N7/24 ,  G06F13/14

CPC分类号： G06F3/0613 ,  G06F3/0656 ,  G06F3/0674 ,  H04N7/17336 ,  H04N7/24

摘要： Buffer space and disk bandwidth resources in a continuous media server are continuously re-allocated in order to optimize the number of continuous media requests which may be concurrently serviced at guaranteed transfer rates using on demand paging. Disk scheduling is provided to ensure that whenever an admitted request references a page of data, the page is available in a buffer for transfer to a client. Data for continuous media data files are stored on disk or held in the buffer to eliminate disk bandwidth limitations associated with concurrently servicing any number or combination of requests, provided buffer space is sufficient. Multiple requests for continuous media data files are selectively included in groups for servicing in order to provide that buffer and disk bandwidth requirements are maintained at a minimum and within available resource capabilities.

摘要翻译： 持续重新分配连续媒体服务器中的缓冲区空间和磁盘带宽资源，以便优化连续媒体请求的数量，可以使用按需分页在保证的传输速率下同时提供服务。 提供磁盘调度以确保每当收到的请求引用一页数据时，该页面在缓冲区中可用于传输到客户端。 连续媒体数据文件的数据存储在磁盘上或保存在缓冲区中，以消除与同时服务任何数量或组合的请求相关联的磁盘带宽限制，只要缓冲区空间就足够了。 连续媒体数据文件的多个请求被选择性地包括在用于服务的组中，以便将缓冲器和磁盘带宽要求保持在最小并且在可用资源能力内。

公开(公告)号：US5720037A

公开(公告)日：1998-02-17

申请号：US260856

申请日：1994-06-16

申请人： Alexandros Biliris ,  Banu Ozden ,  Rajeev Rastogi ,  Abraham Silberschatz

发明人： Alexandros Biliris ,  Banu Ozden ,  Rajeev Rastogi ,  Abraham Silberschatz

IPC分类号： H04N7/173 ,  H04N7/16

CPC分类号： H04N21/2387 ,  H04N7/17336

摘要： A multimedia on-demand server including a randomly accessible library of multimedia programs (such as movies stored on magnetic or optical disks), a limited amount of RAM to buffer and store selected portions of programs retrieved from the library, and an interface that switchably routes program material from the library and RAM buffers to an audience of viewers. The server employs a restricted retrieval strategy and a novel storage allocation scheme that enable different portions of one or more programs to be continuously retrieved and selectively routed to a large number of on-demand viewers, while at the same time minimizing the amount of the RAM required to effect this service. The on-demand server also responds to viewer-generated commands to control the viewing of a program. In a particular embodiment, these commands include video tape player-like operations such as fast-forward, rewind and pause.

摘要翻译： 一种多媒体点播服务器，包括随机访问的多媒体节目库（诸如存储在磁盘或光盘上的电影），有限数量的RAM以缓冲和存储从库中检索的节目的所选部分，以及可切换路由的接口 来自图书馆和RAM缓冲区的节目素材给观众。 服务器采用受限制的检索策略和新颖的存储分配方案，其使一个或多个节目的不同部分能够被连续地检索并且选择性地路由到大量的按需观看者，同时最小化RAM的量 需要实现这项服务。 按需服务器还响应查看器生成的命令来控制程序的查看。 在特定实施例中，这些命令包括诸如快进，快退和暂停的类似磁带播放器的操作。

公开(公告)号：US5964829A

公开(公告)日：1999-10-12

申请号：US624011

申请日：1996-03-27

申请人： Banu Ozden ,  Rajeev Rastogi ,  Abraham Silberschatz

发明人： Banu Ozden ,  Rajeev Rastogi ,  Abraham Silberschatz

IPC分类号： G06F15/173 ,  G06F9/46 ,  G06F9/48 ,  H04N5/765 ,  H04N5/93 ,  H04N7/16 ,  H04N7/173 ,  H04N21/2315 ,  H04N21/262

CPC分类号： H04N7/17336

摘要： A method and apparatus are disclosed for providing enhanced pay per view in a video server. Specifically, the present invention periodically schedules a group of non pre-emptible tasks corresponding to videos in a video server having a predetermined number of processors, wherein each task begins at predetermined periods and has a set of sub-tasks separated by predetermined intervals. To schedule the group of tasks, the present invention divides the tasks into two groups according to whether they may be scheduled on a single processor. The present invention schedules each group separately. For the group of tasks not scheduleable on a single processor, the present invention determines a number of processors required to schedule such group and schedules such tasks to start at a predetermined time. For the group of tasks scheduleable on a single processor, the present invention determines whether such tasks are scheduleable on the available processors using an array of time slots. If the present invention determines that such group of tasks are not scheduleable on the available processors, then the present invention recursively partitions such group of tasks in subsets and re-performs the second determination of scheduleability. Recursive partitioning continues until the group of tasks is deemed scheduleable or no longer partitionable. In the latter case, the group of tasks is deemed not scheduleable.

摘要翻译： 公开了一种用于在视频服务器中提供增强的每次视图的方法和装置。 具体地说，本发明周期性地调度与具有预定数量的处理器的视频服务器中的视频相对应的一组不可预先排除的任务，其中每个任务以预定时段开始并且具有以预定间隔隔开的一组子任务。 为了安排该组任务，本发明根据它们是否可以在单个处理器上进行调度来将任务分成两组。 本发明分别安排每组。 对于在单个处理器上不可调度的任务组，本发明确定了调度这样的组并且计划这些任务在预定时间开始的所需的处理器数量。 对于在单个处理器上可调度的任务组，本发明使用时隙阵列来确定这些任务是否在可用处理器上可调度。 如果本发明确定这样的任务组在可用处理器上是不可调度的，则本发明递归地在子集中划分这样的任务组，并重新执行可调度性的第二确定。 递归分区继续进行，直到任务组被视为可安排或不再可分区。 在后一种情况下，该组任务被视为不可计划。

公开(公告)号：US6079028A

公开(公告)日：2000-06-20

申请号：US839188

申请日：1997-04-23

申请人： Banu Ozden ,  Rajeev Rastogi ,  Prashant J. Shenoy ,  Abraham Silberschatz

发明人： Banu Ozden ,  Rajeev Rastogi ,  Prashant J. Shenoy ,  Abraham Silberschatz

IPC分类号： G06F11/10 ,  G06F11/00

CPC分类号： G06F11/1076 ,  G06F2211/1016

摘要： A continuous media server that provides support for the storage and retrieval of continuous media data at guaranteed rates using one of two fault-tolerant approaches that rely on admission control in order to meet rate guarantees in the event of a failure of the data storage medium that renders part of the continuous media inaccessible. In the first approach, a declustered parity storage scheme is used to uniformly distribute the additional load caused by a disk failure, uniformly across the disks. Contingency bandwidth for a certain number of clips is reserved on each disk in order to retrieve the additional blocks. In the second approach, data blocks in a parity group are prefetched and thus in the event of a disk failure only one additional parity block is retrieved for every data block to be reconstructed. While the second approach generates less additional load in the event of a failure, it has higher buffer requirements. For the second approach, parity blocks can either be stored on a separate parity disk, or distributed among the disks with contingency bandwidth reserved on each disk.

摘要翻译： 一种连续的媒体服务器，其以保证的速率提供对连续媒体数据的存储和检索的支持，使用依赖于准入控制的两种容错方法之一，以便在数据存储介质发生故障的情况下满足速率保证 使部分连续媒体无法访问。 在第一种方法中，使用解聚奇偶校验存储方案来均匀地分布由磁盘故障引起的附加负载，均匀地分布在磁盘上。 为了检索附加的块，在每个磁盘上保留一定数量的剪辑的应急带宽。 在第二种方法中，奇偶校验组中的数据块被预取，因此在发生磁盘故障的情况下，仅针对要重建的每个数据块检索一个附加奇偶校验块。 虽然第二种方法在发生故障时产生较少的额外负载，但它具有较高的缓冲区要求。 对于第二种方法，奇偶校验块可以存储在单独的奇偶校验磁盘上，或者分布在每个磁盘上预留有应急带宽的磁盘之间。

公开(公告)号：US6012080A

公开(公告)日：2000-01-04

申请号：US624013

申请日：1996-03-27

申请人： Banu Ozden ,  Rajeev Rastogi ,  Abraham Silberschatz

发明人： Banu Ozden ,  Rajeev Rastogi ,  Abraham Silberschatz

IPC分类号： G06F12/00 ,  G06F9/48 ,  H04L12/58 ,  H04N7/16 ,  H04N7/173 ,  H04N21/2315 ,  H04N21/262 ,  G06F9/46

CPC分类号： G06F9/4881 ,  H04N21/2312 ,  H04N7/17336

摘要： A method and an apparatus are disclosed for providing enhanced pay per view in a video server. Specifically, the present invention periodically schedules a group of non pre-emptible tasks corresponding to videos in a video server having a predetermined number of processors, wherein each task is defined by a computation time and a period. To schedule the group of tasks, the present invention divides the tasks into two groups according to whether they may be scheduled on less than one processor. The present invention schedules each group separately. For the group of tasks scheduleable on less than one processor, the present invention conducts a first determination of scheduleability. If the first determination of scheduleability deems the group of tasks not scheduleable, then the present invention conducts a second determination of scheduleability. If the second determination of scheduleability also deems the group of tasks not scheduleable, then the present invention recursively partitions the group of tasks in subsets and re-performs the second determination of scheduleability. Recursive partitioning continues until the group of tasks is deemed scheduleable or no longer partitionable. In the latter case, the group of tasks is deemed not scheduleable.

摘要翻译： 公开了一种用于在视频服务器中提供增强的每次视图的方法和装置。 具体地，本发明定期地对具有预定数量的处理器的视频服务器中的视频对应的一组不可预先排除的任务进行调度，其中每个任务由计算时间和周期来定义。 为了安排该组任务，本发明根据它们是否可以在不到一个处理器上进行调度来将任务分成两组。 本发明分别安排每组。 对于可在不到一个处理器上调度的任务组，本发明进行可调度性的第一确定。 如果第一次确定可调度性，则认为该组任务不可计划，则本发明进行可调度性的第二确定。 如果对可调度性的第二确定也认为该组任务不可调度，则本发明递归地分组子集中的任务组并且重新执行可调度性的第二确定。 递归分区继续进行，直到任务组被视为可安排或不再可分区。 在后一种情况下，该组任务被视为不可计划。

公开(公告)号：US5870551A

公开(公告)日：1999-02-09

申请号：US629118

申请日：1996-04-08

申请人： Banu Ozden ,  Rajeev Rastogi ,  Abraham Silberschatz

发明人： Banu Ozden ,  Rajeev Rastogi ,  Abraham Silberschatz

IPC分类号： G06F12/08 ,  G06F3/06 ,  G06F12/12 ,  G06F12/00 ,  G06F13/14 ,  H04N7/16

CPC分类号： G06F12/121

摘要： Two methods are disclosed for storing multimedia data that reduces the amount of disk I/O required by the system and cache misses experienced by the system. The first method determines the future access of each data buffer in a cache memory. Once the future of the data buffer is determined, the data buffer with the maximum future is allocated to store new blocks of data. The method approximates an optimal method of data buffer allocation, by calculating the future of a data buffer, relative to clients that will access the data buffers. The second method orders the clients based on the increasing distance of each client from the previous client; clients release the buffers in this order into a LIFO queue; if a buffer is selected to load a new block of data, the buffer at the head of the LIFO queue is selected.

摘要翻译： 公开了用于存储减少系统所需的盘I / O量和系统经历的高速缓存未命中的多媒体数据的两种方法。 第一种方法确定高速缓冲存储器中每个数据缓冲区的将来访问。 一旦确定了数据缓冲区的未来，则分配具有最大未来的数据缓冲器来存储新的数据块。 该方法通过相对于将访问数据缓冲区的客户端计算数据缓冲区的未来，逼近数据缓冲区分配的最佳方法。 第二种方法是根据每个客户端与以前的客户端的距离不断增加来定购客户端; 客户端将缓冲区按此顺序释放到LIFO队列中; 如果选择缓冲区来加载新的数据块，则选择LIFO队列头部的缓冲区。

公开(公告)号：US5826110A

公开(公告)日：1998-10-20

申请号：US492315

申请日：1995-06-19

申请人： Banu Ozden ,  Rajeev Rastogi ,  Abraham Silberschatz

发明人： Banu Ozden ,  Rajeev Rastogi ,  Abraham Silberschatz

IPC分类号： H04N5/85 ,  G11B20/12 ,  G11B27/00 ,  H04N5/765 ,  H04N5/92 ,  H04N7/173 ,  G06F13/14 ,  G06F13/37

CPC分类号： H04N7/17318 ,  G11B27/002 ,  H04N7/17336

摘要： A method for retrieving video data which has been striped across a plurality of disks using a coarse-grained striping technique. Specifically, and in accordance with an illustrative embodiment of the present invention, the method comprises scheduling the retrieval of a video in response to an incoming request and based on the availability of bandwidth on the disks, and then rescheduling the retrieval of that video to occur at an earlier time, the rescheduling based on a change (i.e., an increase) in the availability of bandwidth on the disks which results from the retrieval of another video being completed. The scheduling and rescheduling may, for example, comprise assigning a disk to the video, where the method further comprises incrementing the disk assigned to the video as each round occurs and beginning the retrieval of the given video when the disk assigned to it is the disk on which the data for the given video begins.

摘要翻译： 一种用于检索已经使用粗粒度条带化技术在多个盘上条带化的视频数据的方法。 具体地说，并且根据本发明的说明性实施例，该方法包括响应于传入请求并且基于磁盘上的带宽的可用性来调度视频的检索，然后重新安排该视频的检索以发生 在更早的时间，基于由完成的另一个视频的检索导致的磁盘上的带宽的可用性的改变（即，增加）来重新安排。 调度和重新调度可以例如包括将磁盘分配给视频，其中该方法还包括在分配给每个轮的时候递增分配给视频的磁盘，并且当分配给它的磁盘是磁盘时开始检索给定的视频 给定视频的数据开始。

公开(公告)号：US5761692A

公开(公告)日：1998-06-02

申请号：US441566

申请日：1995-05-15

申请人： Banu Ozden ,  Rajeev Rastogi ,  Abraham Silberschatz

发明人： Banu Ozden ,  Rajeev Rastogi ,  Abraham Silberschatz

IPC分类号： G06F3/06 ,  G06F17/30 ,  G11B20/10 ,  H04N7/173

CPC分类号： H04N21/2326 ,  G06F17/30017 ,  G06F3/0613 ,  G06F3/0656 ,  G06F3/0659 ,  G06F3/0674 ,  H04N7/17336 ,  Y10S707/99953 ,  Y10S707/99956

摘要： Retrieval of both continuous and non-continuous media data is performed concurrently for multiple requests, where servicing of continuous media data requests at varying rate requirements is guaranteed within a common retrieval period. The common period is selected with respect to the available buffer space and the total disk retrieval times required for servicing multiple requests. Servicing of requests is re-commenced immediately after all admitted requests have been serviced, regardless if the common period has elapsed. High throughput is obtained and transfer rates for a large number of real-time requests are guaranteed by reducing seek latency and eliminating rotational latency so that the buffering requirements for requests are reduced. Disk scheduling techniques are applied for disks having transfer rates which vary from one track to another. Non-continuous media requests are serviced concurrently with continuous media requests by reserving a certain portion of the disk bandwidth for non-continuous media requests in order to provide for low response times. Changing workloads are accommodated by dynamically varying the buffer space allocated to continuous media and non-continuous media requests and by using the time allocated but not utilized for continuous media requests for servicing non-continuous media requests. The disk scheduling techniques are also applicable for disks having varying track sizes and where clips are stored on tracks non-contiguously.

摘要翻译： 对于多个请求同时执行连续和非连续媒体数据的检索，其中在不同的速率要求下的连续媒体数据请求的维护在一个共同检索周期内被保证。 相对于可用的缓冲区空间和服务多个请求所需的总磁盘检索时间选择公共周期。 在所有承认的请求已被服务之后，服务请求将立即重新开始，无论公共期限是否过去。 获得高吞吐量，并通过减少搜索延迟和消除旋转延迟来保证大量实时请求的传输速率，从而降低对请求的缓冲要求。 磁盘调度技术应用于具有从一个轨道到另一个轨道的传输速率的磁盘。 通过为非连续媒体请求预留一部分磁盘带宽以提供低响应时间，非连续媒体请求与连续媒体请求同时服务。 通过动态地改变分配给连续媒体和非连续媒体请求的缓冲区空间以及通过使用分配但不用于维持非连续媒体请求的连续媒体请求的时间来适应变化的工作负载。 磁盘调度技术也可应用于具有不同轨道尺寸的磁盘，并且其中片段非连续地存储在轨道上。

公开(公告)号：US5724543A

公开(公告)日：1998-03-03

申请号：US491755

申请日：1995-06-19

申请人： Banu Ozden ,  Rajeev Rastogi ,  Abraham Silberschatz

发明人： Banu Ozden ,  Rajeev Rastogi ,  Abraham Silberschatz

IPC分类号： H04N5/85 ,  G06F3/06 ,  H04N5/92 ,  H04N7/16 ,  H04N7/173 ,  H04N21/226 ,  H04N21/231 ,  G06F13/14

CPC分类号： G06F3/0601 ,  H04N7/17336 ,  G06F2003/0697

摘要： A method for retrieving video data from a video server, the video data having been stored on a plurality of disks based on a disk striping technique. In accordance with one illustrative embodiment, the method comprises the steps of retrieving a predetermined number of bits from the plurality of disks in the video server, and storing that predetermined number of bits in a buffer memory, wherein the number of bits retrieved and stored is based on the number of disks and on the capacity of the buffer memory. These steps, which together may illustratively constitute one round of the video retrieval process, may be repeated until the entire video has been retrieved and, for example, transmitted to the intended recipient(s) at a required transmission rate.

摘要翻译： 一种用于从视频服务器检索视频数据的方法，所述视频数据已经基于盘分条技术存储在多个盘上。 根据一个说明性实施例，该方法包括以下步骤：从视频服务器中的多个盘中检索预定数量的比特，并将该预定数量的比特存储在缓冲存储器中，其中检索和存储的比特数是 基于磁盘的数量和缓冲存储器的容量。 这些步骤一起可以说明性地构成视频检索过程的一轮，可以重复，直到整个视频被检索并且例如以所需的传输速率发送到预期的接收者。