公开(公告)号：US5999963A

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

申请号：US965934

申请日：1997-11-07

申请人： John Louis Bruno ,  Eran Gabber ,  Banu Ozden ,  Abraham Silberschatz

发明人： John Louis Bruno ,  Eran Gabber ,  Banu Ozden ,  Abraham Silberschatz

IPC分类号： G06F9/48 ,  G06F9/00

CPC分类号： G06F9/4881

摘要： A new scheduling method and policy for shared (server) resources, such as the CPU or disk memory of a multiprogrammed data processor. The scheduling is referred to as Move-To-Rear List Scheduling and it provides a cumulative service guarantee and well as more traditional guarantees such as fairness (proportional sharing) and bounded delay. In typical operation, a list is maintained for a server of processes seeking service from the server. Processes are admitted to the list only when maximum capacity constraints are not violated, and once on the list, are served in a front-to-back order. After receiving service, or upon the occurrence of other events, the position of the process on the list may be changed.

摘要翻译： 用于共享（服务器）资源的新调度方法和策略，例如多编程数据处理器的CPU或磁盘存储器。 调度被称为移动到后端列表调度，它提供了累积的服务保证，以及更传统的保证，如公平（比例共享）和有界延迟。 在典型操作中，为从服务器寻求服务的进程服务器维护一个列表。 只有在没有违反最大容量限制的情况下，进程才能被列入列表，并且在列表中一次以从前到后的顺序提供。 在接收到服务之后，或在发生其他事件时，列表中的进程的位置可以被改变。

公开(公告)号：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的量 需要实现这项服务。 按需服务器还响应查看器生成的命令来控制程序的查看。 在特定实施例中，这些命令包括诸如快进，快退和暂停的类似磁带播放器的操作。

公开(公告)号：US06675229B1

公开(公告)日：2004-01-06

申请号：US09450036

申请日：1999-11-29

申请人： John Louis Bruno ,  José Carlos Brustoloni ,  Eran Gabber ,  Banu Ozden ,  Abraham Silberschatz ,  Amit Singh

发明人： John Louis Bruno ,  José Carlos Brustoloni ,  Eran Gabber ,  Banu Ozden ,  Abraham Silberschatz ,  Amit Singh

IPC分类号： G06F954

CPC分类号： G06F9/5055 ,  G06F2209/5014

摘要： A computer operating system that allows legacy applications to be run automatically with quality of service (QoS) guarantees matching required QoS performance levels. In accordance with the invention, files have QoS requirement attributes that can be set-by users. Additionally, users may interpose a requirement broker between a given legacy application and the operating system. The requirement broker may be in the form of a modified version of a library that is dynamically linked with applications at load time. The requirement broker intercepts certain system calls and automatically requests from the system QoS guarantees in accordance with the QoS requirement attributes of the accessed files, whether local or remote.

摘要翻译： 允许遗留应用程序以服务质量（QoS）自动运行的计算机操作系统保证匹配所需的QoS性能级别。 根据本发明，文件具有可由用户设置的QoS要求属性。 此外，用户可以在给定的遗留应用和操作系统之间插入需求代理。 需求代理可以是在加载时与应用程序动态链接的库的修改版本的形式。 需求代理根据所访问的文件的QoS要求属性（无论是本地还是远程）拦截某些系统调用并根据系统的QoS保证自动请求。

公开(公告)号：US06278998B1

公开(公告)日：2001-08-21

申请号：US09250502

申请日：1999-02-16

申请人： Banu Ozden ,  Sridhar Ramaswamy ,  Abraham Silberschatz

发明人： Banu Ozden ,  Sridhar Ramaswamy ,  Abraham Silberschatz

IPC分类号： G06F1730

CPC分类号： G06F17/30539 ,  G06F2216/03 ,  Y10S707/99931 ,  Y10S707/99933 ,  Y10S707/99935 ,  Y10S707/99936

摘要： A system and method for discovering association rules that display regular cyclic variation over time is disclosed. Such association rules may apply over daily, weekly or monthly (or other) cycles of sales data or the like. A first technique, referred to as the sequential algorithm, treats association rules and cycles relatively independently. Based on the interaction between association rules and time, we employ a new technique called cycle pruning, which reduces the amount of time needed to find cyclic association rules. A second algorithm, the interleaved algorithm, uses cycle pruning and other optimization techniques for discovering cyclic association rules with reduced overhead.

摘要翻译： 公开了一种用于发现随时间显示常规循环变化的关联规则的系统和方法。 这种关联规则可以应用于销售数据等的每日，每周或每月（或其他）周期。 被称为顺序算法的第一种技术相对独立地对待关联规则和循环。 基于关联规则和时间之间的相互作用，我们采用了一种称为循环修剪的新技术，减少了查找循环关联规则所需的时间。 交织算法的第二种算法使用循环修剪和其他优化技术，以减少开销来发现循环关联规则。

公开(公告)号：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队列头部的缓冲区。

公开(公告)号：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.

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

公开(公告)号：US06665732B1

公开(公告)日：2003-12-16

申请号：US09138338

申请日：1998-08-21

申请人： Minos N. Garofalakis ,  Yannis E. Ioannidis ,  Banu Ozden

发明人： Minos N. Garofalakis ,  Yannis E. Ioannidis ,  Banu Ozden

IPC分类号： G06F1516

CPC分类号： H04L65/602 ,  H04L29/06 ,  H04L29/06027 ,  H04L65/80 ,  H04L67/322 ,  H04L69/329

摘要： A system for the effective resource scheduling of composite multimedia objects involves a sequence packing formulation of the composite object scheduling problem and associated efficient algorithms using techniques from pattern matching and multiprocessor scheduling. An associated method of scheduling the provision of composite multimedia objects, each comprising one or more continuous media streams of audio data, video data and other data, where the continuous media streams are of varying bandwidth requirement and duration comprise the steps of; generating composite multimedia objects from the continuous media streams and determining a run-length compressed form for each of the generated composite multimedia objects.

摘要翻译： 用于复合多媒体对象的有效资源调度的系统涉及使用来自模式匹配和多处理器调度的技术的复合对象调度问题的序列打包公式和相关联的有效算法。 一种调度提供复合多媒体对象的相关联的方法，每个复合多媒体对象包括音频数据，视频数据和其他数据的一个或多个连续媒体流，其中连续媒体流具有不同带宽要求和持续时间，包括以下步骤： 从所述连续媒体流生成复合多媒体对象，并为每个所生成的复合多媒体对象确定游程长度压缩形式。

公开(公告)号：US06556578B1

公开(公告)日：2003-04-29

申请号：US09295458

申请日：1999-04-14

申请人： Abraham Silberschatz ,  Banu Ozden ,  John Bruno ,  Huzur Saran

发明人： Abraham Silberschatz ,  Banu Ozden ,  John Bruno ,  Huzur Saran

IPC分类号： H04L1228

CPC分类号： H04L47/29 ,  H04L47/10 ,  H04L47/193 ,  H04L47/32 ,  H04L47/50 ,  H04L47/60 ,  H04L47/6225 ,  H04L47/6255 ,  H04L49/90 ,  H04L49/901 ,  H04L49/9047 ,  H04L49/9078 ,  H04L69/16 ,  H04L69/163

摘要： A method for managing a buffer pool containing a plurality of queues is based on consideration of both (a) when to drop a packet and (b) from which queue the packet should be dropped. According to the method a packet drop is signaled with the global average queue occupancy exceeds a maximum threshold and is signaled on a probabilistic basis when the global occupancy is between a minimum threshold and the maximum threshold. Each queue has a particular local threshold value associated with it and is considered to be “offending” when its buffer occupancy exceeds its local threshold. When a packet drop is signaled, one of the offending queues is selected using a hierarchical, unweighted round robin selection scheme which ensures that offending queues are selected in a fair manner. A packet is then dropped from the selected offending queue.

摘要翻译： 一种用于管理包含多个队列的缓冲池的方法是基于（a）何时丢弃分组和（b）从哪个队列丢弃分组的考虑。 根据该方法，当全局平均队列占用超过最大阈值时用信号通知分组丢弃，并且当全局占用在最小阈值和最大阈值之间时，以概率为基础发信号通知分组丢弃。 每个队列具有与其相关联的特定局部阈值，并且当其缓冲器占用超过其本地阈值时被认为是“违规”的。 当信号通知分组丢弃时，使用分层，未加权的循环选择方案选择违规队列中的一个，以确保以公平的方式选择违规队列。 然后从所选择的违规队列中丢弃一个数据包。