公开(公告)号：US20100195488A1

公开(公告)日：2010-08-05

申请号：US12364520

申请日：2009-02-03

Applicant: Sanjeev Mehrotra ,  Ying-zong Huang ,  Jin Li ,  Sayandeep Sen ,  Manish Jain ,  Sudipta Sengupta

Inventor： Sanjeev Mehrotra ,  Ying-zong Huang ,  Jin Li ,  Sayandeep Sen ,  Manish Jain ,  Sudipta Sengupta

IPC: H04J1/16 ,  H04L12/56 ,  H04L1/00

CPC classification number: H04L47/10 ,  H04J3/0682 ,  H04L1/0002 ,  H04L1/0009 ,  H04L1/0015 ,  H04L1/1867 ,  H04L47/115 ,  H04L47/193 ,  H04L47/25 ,  H04L47/283 ,  H04L47/37 ,  Y02D50/10

Abstract: Transmission delays are minimized when packets are transmitted from a source computer over a network to a destination computer. The source computer measures the network's available bandwidth, forms a sequence of output packets from a sequence of data packets, and transmits the output packets over the network to the destination computer, where the transmission rate is ramped up to the measured bandwidth. In conjunction with the transmission, the source computer monitors a transmission delay indicator which it computes using acknowledgement packets it receives from the destination computer. Whenever the indicator specifies that the transmission delay is increasing, the source computer reduces the transmission rate until the indicator specifies that the delay is unchanged. The source computer dynamically decides whether each output packet will be a forward error correction packet or a single data packet, where the decision is based on minimizing the expected transmission delays.

Abstract translation: 当数据包通过网络从源计算机传输到目标计算机时，传输延迟最小化。 源计算机测量网络的可用带宽，形成来自一系列数据分组的输出分组序列，并通过网络将输出分组发送到目标计算机，其中传输速率升高到测量带宽。 结合传输，源计算机监视传输延迟指示符，其使用从目的地计算机接收的确认分组来计算它。 每当指示符指示传输延迟增加时，源计算机降低传输速率，直到指示符指定延迟不变。 源计算机动态地确定每个输出分组是否将是前向纠错分组或单个数据分组，其中决定基于最小化期望的传输延迟。

公开(公告)号：US20130346672A1

公开(公告)日：2013-12-26

申请号：US13531455

申请日：2012-06-22

Applicant: Sudipta Sengupta ,  Jin Li ,  Cheng Huang ,  Timothy Andrew Pritchett ,  Christopher Broder Wilson

Inventor： Sudipta Sengupta ,  Jin Li ,  Cheng Huang ,  Timothy Andrew Pritchett ,  Christopher Broder Wilson

IPC: G06F12/02 ,  G06F12/08

CPC classification number: G06F12/0871 ,  G06F12/0897 ,  G06F12/12

Abstract: The subject disclosure is directed towards a multi-tiered cache having cache tiers with different access properties. Objects are written to a selected a tier of the cache based upon object-related properties and/or cache-related properties. In one aspect, objects are stored in an active log among a plurality of logs. The active log is sealed upon reaching a target size, with a new active log opened. Garbage collecting is performed on a sealed log, such as the sealed log with the most garbage therein.

Abstract translation: 主题公开针对具有不同访问属性的高速缓存层的多层缓存。 基于对象相关属性和/或缓存相关属性，将对象写入高速缓存的选定层。 在一个方面，对象被存储在多个日志中的活动日志中。 活动日志在达到目标大小时被打开，新的活动日志打开。 垃圾收集是在密封的日志上进行的，例如其中垃圾最多的密封日志。

公开(公告)号：US20120102298A1

公开(公告)日：2012-04-26

申请号：US12908153

申请日：2010-10-20

Applicant: Sudipta Sengupta ,  Biplob Kumar Debnath ,  Jin Li

Inventor： Sudipta Sengupta ,  Biplob Kumar Debnath ,  Jin Li

IPC: G06F12/10 ,  G06F12/00

Abstract: Described is using flash memory (or other secondary storage), RAM-based data structures and mechanisms to access key-value pairs stored in the flash memory using only a low RAM space footprint. A mapping (e.g. hash) function maps key-value pairs to a slot in a RAM-based index. The slot includes a pointer that points to a bucket of records on flash memory that each had keys that mapped to the slot. The bucket of records is arranged as a linear-chained linked list, e.g., with pointers from the most-recently written record to the earliest written record. Also described are compacting non-contiguous records of a bucket onto a single flash page, and garbage collection. Still further described is load balancing to reduce variation in bucket sizes, using a bloom filter per slot to avoid unnecessary searching, and splitting a slot into sub-slots.

Abstract translation: 描述的是使用闪速存储器（或其他辅助存储器），基于RAM的数据结构和机制来访问存储在闪存中的键值对，仅使用低的RAM空间。 映射（例如散列）功能将键值对映射到基于RAM的索引中的时隙。 插槽包括一个指向闪存中的一桶记录的指针，每个记录都具有映射到插槽的键。 记录的桶被布置为线性链接的链表，例如具有从最近写入的记录到最早的书面记录的指针。 还描述了将桶的不连续记录压缩到单个闪存页面上以及垃圾收集。 还进一步描述的是负载平衡以减少桶大小的变化，使用每时隙的布隆过滤器来避免不必要的搜索，并且将时隙分割成子时隙。

公开(公告)号：US08082358B2

公开(公告)日：2011-12-20

申请号：US12242913

申请日：2008-09-30

Applicant: Jiajun Wang ,  Cheng Huang ,  Sudipta Sengupta ,  Jin Li

Inventor： Jiajun Wang ,  Cheng Huang ,  Sudipta Sengupta ,  Jin Li

IPC: G06F15/16

CPC classification number: H04L47/19 ,  H04L47/10 ,  H04L47/12 ,  H04L47/25 ,  H04L67/104

Abstract: An ISP-friendly rate allocation system and method that reduces network traffic across ISP boundaries in a peer-to-peer (P2P) network, Embodiments of the system and method continuously solve a global optimization problem and dictate accordingly how much bandwidth is allocated on each connection. Embodiments of the system and method minimize load on a server in communication with the P2P network, minimize ISP-unfriendly traffic while keeping the minimum server load unaffected, and maximize peer prefetching. Two different techniques are used to compute rate allocation, including a utility function optimization technique and a minimum cost flow formulation technique. The utility function optimization technique constructs a utility function and optimizes that utility function. The minimum cost flow formulation technique generates a minimum cost flow formulation using a bipartite graph have a vertices set and an edges set. A distributed minimum cost flow formulation is solved using Lagrangian multipliers.

Abstract translation: 一种ISP友好的速率分配系统和方法，可减少对等（P2P）网络中ISP边界的网络流量，系统和方法的实施方案不断解决全局优化问题，并据此规定每个网络上分配多少带宽 连接。 系统和方法的实施例最小化与P2P网络通信的服务器上的负载，从而最小化ISP不友好的业务，同时保持最小服务器负载不受影响，并最大化对等体预取。 使用两种不同的技术来计算速率分配，包括效用函数优化技术和最低成本流量制定技术。 效用函数优化技术构建效用函数并优化该效用函数。 最小成本流量制定技术使用具有顶点集合和边集合的二分图生成最小成本流程公式。 使用拉格朗日乘数解决分布式最小成本流公式。

公开(公告)号：US20110276780A1

公开(公告)日：2011-11-10

申请号：US12979644

申请日：2010-12-28

Applicant: Sudipta Sengupta ,  Biplob Debnath ,  Jin Li ,  Ronakkumar N. Desai ,  Paul Adrian Oltean

Inventor： Sudipta Sengupta ,  Biplob Debnath ,  Jin Li ,  Ronakkumar N. Desai ,  Paul Adrian Oltean

IPC: G06F12/08

CPC classification number: G06F12/0862 ,  G06F12/0866 ,  G06F17/30159

Abstract: The subject disclosure is directed towards a data deduplication technology in which a hash index service's index maintains a hash index in a secondary storage device such as a hard drive, along with a compact index table and look-ahead cache in RAM that operate to reduce the I/O to access the secondary storage device during deduplication operations. Also described is a session cache for maintaining data during a deduplication session, and encoding of a read-only compact index table for efficiency.

公开(公告)号：US20110276744A1

公开(公告)日：2011-11-10

申请号：US12773859

申请日：2010-05-05

Applicant: Sudipta Sengupta ,  Biplob Kumar Debnath ,  Jin Li

Inventor： Sudipta Sengupta ,  Biplob Kumar Debnath ,  Jin Li

IPC: G06F12/02 ,  G06F12/10 ,  G06F12/00

CPC classification number: G06F12/0246 ,  G06F12/0866 ,  G06F12/0897 ,  G06F12/123 ,  G06F2212/222 ,  G11C7/1072

Abstract: Described is using flash memory, RAM-based data structures and mechanisms to provide a flash store for caching data items (e.g., key-value pairs) in flash pages. A RAM-based index maps data items to flash pages, and a RAM-based write buffer maintains data items to be written to the flash store, e.g., when a full page can be written. A recycle mechanism makes used pages in the flash store available by destaging a data item to a hard disk or reinserting it into the write buffer, based on its access pattern. The flash store may be used in a data deduplication system, in which the data items comprise chunk-identifier, metadata pairs, in which each chunk-identifier corresponds to a hash of a chunk of data that indicates. The RAM and flash are accessed with the chunk-identifier (e.g., as a key) to determine whether a chunk is a new chunk or a duplicate.

Abstract translation: 描述的是使用闪存，基于RAM的数据结构和机制来提供用于在闪存页中缓存数据项（例如键值对）的闪存。 基于RAM的索引将数据项映射到闪存页面，并且基于RAM的写入缓冲器保持要写入闪存存储器的数据项目，例如当可以写入全页时。 回收机制使得通过将数据项降级到硬盘或将其重新插入到写入缓冲器中，基于其访问模式，可用于闪存存储器中的使用页面。 闪存存储器可以用在数据重复数据删除系统中，其中数据项包括块标识符，元数据对，其中每个块标识符对应于指示的数据块的散列。 使用块标识符（例如，作为密钥）来访问RAM和闪存，以确定块是新的块还是重复的。

公开(公告)号：US07738406B2

公开(公告)日：2010-06-15

申请号：US12247431

申请日：2008-10-08

Applicant: Shao Liu ,  Sudipta Sengupta ,  Mung Chiang ,  Jin Li ,  Philip Andrew Chou

Inventor： Shao Liu ,  Sudipta Sengupta ,  Mung Chiang ,  Jin Li ,  Philip Andrew Chou

IPC: H04L12/28

CPC classification number: H04L45/00 ,  H04L45/48

Abstract: Peer-to-peer communications sessions involve the transmission of one or more data streams from a source to a set of receivers that may redistribute portions of the data stream via a set of routing trees. Achieving a comparatively high, sustainable data rate throughput of the data stream(s) may be difficult due to the large number of available routing trees, as well as pertinent variations in the nature of the communications session (e.g., upload communications caps, network link caps, the presence or absence of helpers, and the full or partial interconnectedness of the network.) The selection of routing trees may be facilitated through the representation of the node set according to a linear programming model, such as a primal model or a linear programming dual model, and iterative processes for applying such models and identifying low-cost routing trees during an iteration.

Abstract translation: 对等通信会话涉及将一个或多个数据流从源传输到可以通过一组路由树重新分配数据流的部分的一组接收机。 由于大量的可用路由树以及通信会话性质的相关变化（例如，上传通信上限，网络链路），实现数据流的相对较高，可持续的数据速率吞吐量可能是困难的 帽子，帮助者的存在或不存在以及网络的全部或部分互连性）。可以通过根据线性规划模型（例如原始模型或线性的）的节点集合的表示来促进路由树的选择 编程双重模型，以及迭代过程，用于应用此类模型，并在迭代期间识别低成本路由树。

公开(公告)号：US20100085979A1

公开(公告)日：2010-04-08

申请号：US12247431

申请日：2008-10-08

Applicant: Shao Liu ,  Sudipta Sengupta ,  Mung Chiang ,  Jin Li ,  Philip Andrew Chou

Inventor： Shao Liu ,  Sudipta Sengupta ,  Mung Chiang ,  Jin Li ,  Philip Andrew Chou

IPC: H04L12/56

CPC classification number: H04L45/00 ,  H04L45/48

Abstract: Peer-to-peer communications sessions involve the transmission of one or more data streams from a source to a set of receivers that may redistribute portions of the data stream via a set of routing trees. Achieving a comparatively high, sustainable data rate throughput of the data stream(s) may be difficult due to the large number of available routing trees, as well as pertinent variations in the nature of the communications session (e.g., upload communications caps, network link caps, the presence or absence of helpers, and the full or partial interconnectedness of the network.) The selection of routing trees may be facilitated through the representation of the node set according to a linear programming model, such as a primal model or a linear programming dual model, and iterative processes for applying such models and identifying low-cost routing trees during an iteration.

Abstract translation: 对等通信会话涉及将一个或多个数据流从源传输到可以通过一组路由树重新分配数据流的部分的一组接收器。 由于大量的可用路由树以及通信会话性质的相关变化（例如，上传通信上限，网络链路），实现数据流的相对较高，可持续的数据速率吞吐量可能是困难的 帽子，帮助者的存在或不存在以及网络的全部或部分互连性）。可以通过根据线性规划模型（例如原始模型或线性的）的节点集合的表示来促进路由树的选择 编程双重模型，以及迭代过程，用于应用此类模型，并在迭代期间识别低成本路由树。

公开(公告)号：US09110936B2

公开(公告)日：2015-08-18

申请号：US12979748

申请日：2010-12-28

Applicant: Jin Li ,  Sudipta Sengupta ,  Ran Kalach ,  Ronakkumar N. Desai ,  Paul Adrian Oltean ,  James Robert Benton

Inventor： Jin Li ,  Sudipta Sengupta ,  Ran Kalach ,  Ronakkumar N. Desai ,  Paul Adrian Oltean ,  James Robert Benton

IPC: G06F17/30

CPC classification number: G06F17/30371 ,  G06F17/30156 ,  G06F17/30303 ,  G06F17/30327 ,  G06F17/3033 ,  G06F17/30489

Abstract: The subject disclosure is directed towards a data deduplication technology in which a hash index service's index is partitioned into subspace indexes, with less than the entire hash index service's index cached to save memory. The subspace index is accessed to determine whether a data chunk already exists or needs to be indexed and stored. The index may be divided into subspaces based on criteria associated with the data to index, such as file type, data type, time of last usage, and so on. Also described is subspace reconciliation, in which duplicate entries in subspaces are detected so as to remove entries and chunks from the deduplication system. Subspace reconciliation may be performed at off-peak time, when more system resources are available, and may be interrupted if resources are needed. Subspaces to reconcile may be based on similarity, including via similarity of signatures that each compactly represents the subspace's hashes.

Abstract translation: 本发明涉及一种数据重复数据删除技术，其中散列索引服务的索引被分割成子空间索引，其中小于整个散列索引服务的索引来缓存存储器。 访问子空间索引以确定数据块是否已经存在或需要进行索引和存储。 索引可以根据与索引的数据相关联的标准被划分为子空间，例如文件类型，数据类型，上次使用的时间等等。 还描述了子空间协调，其中检测子空间中的重复条目，以便从重复数据删除系统中删除条目和块。 当更多的系统资源可用时，子空间协调可以在非高峰时间执行，并且如果需要资源，则可能被中断。 调和的子空间可以基于相似性，包括通过每个紧密地表示子空间的散列的签名的相似性。

公开(公告)号：US20130282964A1

公开(公告)日：2013-10-24

申请号：US13919727

申请日：2013-06-17

Applicant: Sudipta Sengupta ,  Biplob Kumar Debnath ,  Jin Li

Inventor： Sudipta Sengupta ,  Biplob Kumar Debnath ,  Jin Li

IPC: G06F12/02

CPC classification number: G06F12/0246 ,  G06F12/0866 ,  G06F12/0897 ,  G06F12/123 ,  G06F2212/222 ,  G11C7/1072

Abstract: Described is using flash memory, RAM-based data structures and mechanisms to provide a flash store for caching data items (e.g., key-value pairs) in flash pages. A RAM-based index maps data items to flash pages, and a RAM-based write buffer maintains data items to be written to the flash store, e.g., when a full page can be written. A recycle mechanism makes used pages in the flash store available by destaging a data item to a hard disk or reinserting it into the write buffer, based on its access pattern. The flash store may be used in a data deduplication system, in which the data items comprise chunk-identifier, metadata pairs, in which each chunk-identifier corresponds to a hash of a chunk of data that indicates. The RAM and flash are accessed with the chunk-identifier (e.g., as a key) to determine whether a chunk is a new chunk or a duplicate.