公开(公告)号：US07596544B2

公开(公告)日：2009-09-29

申请号：US11025355

申请日：2004-12-29

申请人： Sumit Ganguly ,  Minos Garofalakis ,  Rajeev Rastogi

发明人： Sumit Ganguly ,  Minos Garofalakis ,  Rajeev Rastogi

IPC分类号： G06F7/00

CPC分类号： G06F17/30469 ,  Y10S707/99932

摘要： A method of estimating set-expression cardinalities over data streams with guaranteed small maintenance time per data-element update. The method only examines each data element once and uses a limited amount of memory. The time-efficient stream synopsis extends 2-level hash-sketches by randomly, but uniformly, pre-hashing data-elements prior to logarithmically hashing them to a first-level hash-table. This generates a set of independent 2-level hash-sketches. The set-union cardinality can be estimated by determining the smallest hash-bucket index j at which only a predetermined fraction of the b hash-buckets has a non-empty union |A∪B|. Once a set-union cardinality is estimated, general set-expression cardinalities may be estimated by counting witness elements for the set-expression, i.e., those first-level hash-buckets that are both a singleton for the set-expression and a set-union singleton. The set-expression cardinality is the set-union cardinality times the number of witness elements divided by the number of hash-buckets.

摘要翻译： 一种估计数据流上的设置表达式基数的方法，每个数据元素更新保证小的维护时间。 该方法仅检查每个数据元素一次并使用有限的内存。 时间有效的流摘要通过随机，但统一地将数据元素进行对数散列之前的第一级散列表来扩展二级散列草图。 这产生一组独立的2级散列草图。 可以通过确定最小的哈希桶索引j来估计设置联合的基数，其中只有预定的b个哈希桶的一部分具有非空联合|A∪B|。 一旦估计了一个组合基数，就可以通过对集表达式的见证元素进行计数来估计一般的集合表示基数，即那些既是集合表达式的单例的一级哈希数据包， 联合单身人士 set-expression的基数是set-union的基数乘以证人的数量除以哈希桶的数量。

公开(公告)号：US20090006346A1

公开(公告)日：2009-01-01

申请号：US11770926

申请日：2007-06-29

申请人： Kanthi C N ,  Naidu K V M ,  Rajeev Rastogi ,  Scott Satkin

发明人： Kanthi C N ,  Naidu K V M ,  Rajeev Rastogi ,  Scott Satkin

IPC分类号： G06F17/30

CPC分类号： G06F17/30463 ,  G06F17/30412 ,  G06F17/30454 ,  G06F17/30548 ,  G06F17/30864

摘要： Improved techniques are disclosed for processing data stream queries wherein a data stream is obtained, a set of aggregate queries to be executed on the data stream is obtained, and a query plan for executing the set of aggregate queries on the data stream is generated. In a first method, the generated query plan includes generating at least one intermediate aggregate query, wherein the intermediate aggregate query combines a subset of aggregate queries from the set of aggregate queries so as to pre-aggregate data from the data stream prior to execution of the subset of aggregate queries such that the generated query plan is optimized for computational expense based on a given cost model. In a second method, the generated query plan includes identifying similar filters in two or more aggregate queries of the set of aggregate queries and combining the similar filters into a single filter such that the single filter is usable to pre-filter data input to the two or more aggregate queries.

摘要翻译： 公开了用于处理数据流查询的改进技术，其中获得数据流，获得要在数据流上执行的一组聚合查询，并且生成用于在数据流上执行聚合查询集合的查询计划。 在第一种方法中，生成的查询计划包括生成至少一个中间聚合查询，其中中间聚合查询组合来自聚合查询集合的聚合查询的子集，以便在执行之前从数据流预聚合数据 聚合查询的子集，使得生成的查询计划基于给定的成本模型被优化用于计算费用。 在第二种方法中，所生成的查询计划包括在集合查询集合的两个或多个聚合查询中识别类似的过滤器，并将类似的过滤器组合成单个过滤器，使得单个过滤器可用于预先过滤输入到两个 或更多聚合查询。

公开(公告)号：US20080175169A1

公开(公告)日：2008-07-24

申请号：US11656465

申请日：2007-01-23

申请人： Supratim Deb ,  Srinivas Kashyap ,  Naidu K V M ,  Rajeev Rastogi ,  Anand Srinivasan

发明人： Supratim Deb ,  Srinivas Kashyap ,  Naidu K V M ,  Rajeev Rastogi ,  Anand Srinivasan

IPC分类号： H04L12/28

CPC分类号： H04L67/104 ,  H04L45/46 ,  H04L67/1046 ,  H04L67/1051 ,  H04L67/12

摘要： A method of grouping nodes within a distributed network is provided. The example method includes performing a leader node self determination operation by which each node within the distributed network determines whether to become a leader node or a non-leader node, each leader node being the leader of a group including at least one node. Next, requests are sent, from each leader node, requesting at least one non-leader node to join the group associated with the leader node. First received requests are accepted, at each non-leader node, such that accepting non-leader nodes transition from a non-leader node to a dependent node dependent upon the requesting leader node. A next set of requests are sent, from each remaining non-leader node, requesting to join the group associated with at least one leader node. A determination is made, at each requested leader node, as to whether to accept the non-leader node into the group associated with the requested leader node. Based on the determination, at each requested leader node, the non-leader node is either accepted into the group associated with the requested leader node, or is alternatively rejected from the group.

摘要翻译： 提供了一种在分布式网络内对节点进行分组的方法。 示例性方法包括执行前导节点自我确定操作，通过该前导节点自我确定操作，分布式网络内的每个节点确定是否成为领导节点或非前导节点，每个首领节点是包括至少一个节点的组的首领。 接下来，从每个领导节点发送请求，请求至少一个非前导节点加入与该领导节点相关联的组。 在每个非前导节点处接收第一接收的请求，使得接受非前导节点从非前导节点到依赖于请求的领导节点的依赖节点的转换。 从每个剩余的非前导节点发送下一组请求，请求加入与至少一个前导节点相关联的组。 在每个请求的领导节点处，确定是否将非前导节点接受到与所请求的领导节点相关联的组中。 基于确定，在每个请求的领导节点处，非前导节点被接受到与所请求的领导节点相关联的组中，或者被替代地从组中被拒绝。

公开(公告)号：US07197040B2

公开(公告)日：2007-03-27

申请号：US10186761

申请日：2002-07-01

申请人： Thomas C. Bressoud ,  Rajeev Rastogi ,  Mark A. Smith

发明人： Thomas C. Bressoud ,  Rajeev Rastogi ,  Mark A. Smith

IPC分类号： H04L12/28 ,  G06F15/173 ,  G06F9/46

CPC分类号： H04L47/10 ,  H04L45/04 ,  H04L45/30 ,  H04L45/38 ,  H04L47/125

摘要： A system for, and method of, configuring border gateway selection for transit traffic flows in a computer network. In one embodiment, the system includes: (1) a border gateway modeler that builds a model of cooperating border gateways, the model including capacities of the border gateways and (2) a traffic flow optimizer, associated with the border gateway modeler, that initially assigns traffic to the border gateways in accordance with a generalized assignment problem and subsequently reassigns the traffic to the border gateways based on cost until the capacities are respected.

摘要翻译： 一种用于在计算机网络中为过境业务流配置边界网关选择的系统和方法。 在一个实施例中，系统包括：（1）构建协作边界网关模型的边界网关建模器，该模型包括边界网关的容量，以及（2）与边界网关建模器相关联的业务流优化器， 根据广义分配问题向边界网关分配流量，随后根据成本将流量重新分配给边界网关，直到容量得到尊重。

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

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

公开(公告)号：US09171006B2

公开(公告)日：2015-10-27

申请号：US11783137

申请日：2007-04-06

申请人： Naidu Kvm ,  Rajeev Rastogi ,  Jeyashankher Sr ,  Anand Srinivasan

发明人： Naidu Kvm ,  Rajeev Rastogi ,  Jeyashankher Sr ,  Anand Srinivasan

IPC分类号： G06F17/30

CPC分类号： H04L67/1095 ,  G06F17/30132 ,  H04L67/1097 ,  H04L67/2847

摘要： Disclosed is a mobile station having an expanded storage space, and a method of retrieving a file stored in a remote storage server. The method may include determining whether the file is locally stored or remotely stored, deleting files in a local storage to provide space if the file is determined to reside in a remote storage server, downloading the file from a remote storage server over the Internet by prefetching a portion of the file from the remote storage server, and opening the prefetched portion of the file while concurrently downloading a remaining portion of the file from the remote storage server.

摘要翻译： 公开了具有扩展的存储空间的移动台以及检索存储在远程存储服务器中的文件的方法。 该方法可以包括确定文件是本地存储还是远程存储，如果文件被确定驻留在远程存储服务器中，则删除本地存储器中的文件以提供空间，通过预取来从远程存储服务器通过因特网下载文件 来自远程存储服务器的文件的一部分，并且在同时从远程存储服务器下载文件的剩余部分的同时打开文件的预取部分。

公开(公告)号：US08028050B2

公开(公告)日：2011-09-27

申请号：US10462215

申请日：2003-06-13

申请人： Giuseppe F. Italiano ,  Rajeev Rastogi ,  Bulent Yener

发明人： Giuseppe F. Italiano ,  Rajeev Rastogi ,  Bulent Yener

IPC分类号： G06F15/177 ,  G06F15/173

CPC分类号： H04L63/0272 ,  H04L12/4641 ,  H04L45/22 ,  H04L45/28 ,  H04L45/48

摘要： Restoration is provided in a communication system having two or more VPN endpoints coupled together through a network comprising a number of nodes interconnected through edges. VPN endpoints coupled through the network are adapted to communicate through a single connection with multiple other VPN endpoints. The single connection may be a VPN hose connection. A restoration topology, comprising backup edges corresponding to primary edges in the network, is determined for the network. A given primary edge is replaced with one or more backup edges if the given primary edge fails. A graph may represent the network and a tree may represent the connections in the network for VPNs connecting the VPN endpoints. The graph can be reduced to a second graph by determining shortest paths between each node in the tree and creating the backup edges from the shortest paths. The second graph can be reduced to a third graph by adding additional backup edges from tree nodes having non-tree edges to least common ancestor nodes. The third graph can be used to create a two-edge connected tree.

摘要翻译： 在具有通过包括通过边缘互连的多个节点的网络的网络耦合在一起的两个或更多个VPN端点的通信系统中提供恢复。 通过网络耦合的VPN端点适于通过与多个其他VPN端点的单个连接进行通信。 单个连接可能是VPN软件连接。 为网络确定包括与网络中的主边缘相对应的备份边缘的恢复拓扑。 如果给定的主边缘发生故障，给定的主边缘将被一个或多个备用边替换。 图表可以表示网络，并且树可以表示网络中连接VPN端点的VPN的连接。 通过确定树中每个节点之间的最短路径并从最短路径创建备份边，可将图形简化为第二个图。 通过从具有非树形边缘的树节点向最不常见的祖先节点添加额外的备份边，可以将第二个图形简化为第三个图形。 第三个图可用于创建一个双边连接的树。