公开(公告)号：US20100085979A1

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

申请号：US12247431

申请日：2008-10-08

申请人： Shao Liu ,  Sudipta Sengupta ,  Mung Chiang ,  Jin Li ,  Philip Andrew Chou

发明人： Shao Liu ,  Sudipta Sengupta ,  Mung Chiang ,  Jin Li ,  Philip Andrew Chou

IPC分类号： H04L12/56

CPC分类号： H04L45/00 ,  H04L45/48

摘要： 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.

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

公开(公告)号：US07561534B2

公开(公告)日：2009-07-14

申请号：US10880887

申请日：2004-06-30

申请人： Mansoor Ali Khan Alicherry ,  Iraj Saniee ,  Sudipta Sengupta

发明人： Mansoor Ali Khan Alicherry ,  Iraj Saniee ,  Sudipta Sengupta

IPC分类号： H04L12/28

CPC分类号： H04L45/28 ,  H04L45/00 ,  H04L45/123 ,  H04L45/124 ,  H04L45/22

摘要： A number of techniques are described for routing methods that improve resistance to faults affecting groups of links subject to common risks. One of these techniques accounts for failure potentials in physical networks by considering shared risk link groups separately from performance and costs metrics in determining a primary routing path and a backup path. A shared risk link group (SRLG) is an attribute attached to a link to identify edges that have physical links in common and can therefore be simultaneously disrupted due to a single fault. Another technique considers node disjointness and provides a solution of two paths that are as node disjoint as possible and minimizes administrative costs. The techniques may further be combined in a priority order thereby providing a solution of at least two paths that are strictly SRLG disjoint, as node-disjoint as possible, and have minimum administrative costs. Due to the priority order of evaluation and typical network physical configurations of links, with the links associated common fault SRLGs, the priority ordering technique is very efficient in determining at least two paths for routing between a source and destination node.

摘要翻译： 描述了一些技术，用于路由方法，这些方法提高了对存在常见风险的链接组的故障的抵抗力。 这些技术之一通过在确定主要路由路径和备用路径时与性能和成本指标分开考虑共享风险链路组来解决物理网络中的故障潜能。 共享风险链接组（SRLG）是附加到链接的属性，用于识别具有共同物理链路的边缘，因此可能由于单个故障而同时中断。 另一种技术考虑到节点不相交，并提供了尽可能节点不相交的两条路径的解决方案，并将管理成本降至最低。 这些技术可以进一步以优先级顺序组合，从而提供严格SRLG不相交的至少两条路径的解决方案，作为节点不相交并且具有最小的管理成本。 由于评估的优先级顺序和链路的典型网络物理配置，链路与公共故障SRLGs相关联，所以优先级排序技术在确定用于在源节点和目的地节点之间路由的至少两个路径方面是非常有效的。

公开(公告)号：US20050265255A1

公开(公告)日：2005-12-01

申请号：US11141257

申请日：2005-05-31

申请人： Muralidharan Kodialam ,  Tirunell Lakshman ,  Sudipta Sengupta

发明人： Muralidharan Kodialam ,  Tirunell Lakshman ,  Sudipta Sengupta

IPC分类号： H04L12/56 ,  H04L12/28 ,  H04L12/26

CPC分类号： H04L45/12 ,  H04L45/04 ,  H04L45/24 ,  H04L47/125

摘要： A method for supporting recovery from failure of a node in a network of nodes interconnected by links, wherein the failed node is in a path providing a service level between an ingress point and an egress point of the network, comprises: (a) selecting a set of one or more intermediate nodes between the ingress point and the egress point, the set excluding the failed node; (b) determining, based on available bandwidth of the network, a non-zero fraction of the service level to route from the ingress point to each intermediate node; (c) implementing, during a first routing phase, a first routing method to determine one or more paths from the ingress point to each intermediate node for routing the corresponding fraction of the service level; and (d) implementing, during a second routing phase, a second routing method to determine one or more paths from each intermediate node to the egress point for routing the corresponding fraction of the service level.

摘要翻译： 一种用于支持通过链路互连的节点网络中的节点的故障恢复的方法，其中所述故障节点处于提供所述网络的入口点和出口点之间的服务水平的路径中，包括：（a）选择 在入口点和出口点之间的一个或多个中间节点的集合，不包括故障节点的集合; （b）基于网络的可用带宽确定从入口点到每个中间节点路由的服务级别的非零分数; （c）在第一路由阶段期间实施第一路由方法，以确定从入口点到每个中间节点的一条或多条路径，用于路由服务级别的相应部分; 以及（d）在第二路由阶段期间实施第二路由方法，以确定从每个中间节点到出口点的一条或多条路径，用于路由服务级别的相应部分。

公开(公告)号：US06778531B1

公开(公告)日：2004-08-17

申请号：US09677009

申请日：2000-09-29

申请人： Muralidharan S. Kodialam ,  Tirnuell V. Lakshman ,  Sudipta Sengupta

发明人： Muralidharan S. Kodialam ,  Tirnuell V. Lakshman ,  Sudipta Sengupta

IPC分类号： H04L1228

CPC分类号： H04L45/302 ,  H04L12/18 ,  H04L45/00 ,  H04L45/125 ,  H04L45/16 ,  H04L45/50

摘要： A packet network of interconnected nodes employs a method of routing with service-level guarantees to determine a path through the network for a requested multicast, label-switched path Each of the nodes includes one or more routers that forward packets based on a forwarding table constructed from a directed tree determined in accordance with the method of multicast routing with service-level guarantees. For a first implementation, a heuristic algorithm uses a scaling phase that iteratively adjusts a maximum arc capacity, determines the resulting tree for the iteration, and selects the tree as the routing tree that provides the “maximum” flow. For a second implementation, the heuristic algorithm computes maximum multicast flows and determines links in the network that are “critical” to satisfy future multicast routing requests. A multicast routing tree is selected such that provisioning the flows over its links “minimally interferes” with capacity of paths needed for future demands.

摘要翻译： 互连节点的分组网络采用路由服务级别保证的方法来确定针对所请求的多播的路由，标签交换路径每个节点包括一个或多个基于构造的转发表转发分组的路由器 从根据具有服务级别保证的多播路由方法确定的有向树。 对于第一个实现，启发式算法使用迭代地调整最大电弧容量的缩放阶段，确定迭代的结果树，并选择该树作为提供“最大”流的路由树。 对于第二个实现，启发式算法计算最大组播流，并确定网络中“关键”的链路以满足未来的组播路由请求。 选择组播路由树，使得通过其链路的流量以最小限度地干扰未来需求所需路径的容量。

公开(公告)号：US09110936B2

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

申请号：US12979748

申请日：2010-12-28

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

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

IPC分类号： G06F17/30

CPC分类号： G06F17/30371 ,  G06F17/30156 ,  G06F17/30303 ,  G06F17/30327 ,  G06F17/3033 ,  G06F17/30489

摘要： 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.

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

公开(公告)号：US20130282964A1

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

申请号：US13919727

申请日：2013-06-17

申请人： Sudipta Sengupta ,  Biplob Kumar Debnath ,  Jin Li

发明人： Sudipta Sengupta ,  Biplob Kumar Debnath ,  Jin Li

IPC分类号： G06F12/02

CPC分类号： G06F12/0246 ,  G06F12/0866 ,  G06F12/0897 ,  G06F12/123 ,  G06F2212/222 ,  G11C7/1072

摘要： 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.

公开(公告)号：US08553540B2

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

申请号：US12762016

申请日：2010-04-16

申请人： Sanjeev Mehrotra ,  Tong L. Wynn ,  Jin Li ,  Sudipta Sengupta

发明人： Sanjeev Mehrotra ,  Tong L. Wynn ,  Jin Li ,  Sudipta Sengupta

IPC分类号： H04L12/26

CPC分类号： H04L47/25 ,  H04L47/22 ,  H04L47/2416 ,  H04L47/29 ,  H04L47/30

摘要： In various embodiments, methods and systems are disclosed for a hybrid rate plus window based congestion protocol that controls the rate of packet transmission into the network and provides low queuing delay, practically zero packet loss, fair allocation of network resources amongst multiple flows, and full link utilization. In one embodiment, a congestion window may be used to control the maximum number of outstanding bits, a transmission rate may be used to control the rate of packets entering the network (packet pacing), a queuing delay based rate update may be used to control queuing delay within tolerated bounds and minimize packet loss, and aggressive ramp-up/graceful back-off may be used to fully utilize the link capacity and additive-increase, multiplicative-decrease (AIMD) rate control may be used to provide fairness amongst multiple flows.

摘要翻译： 在各种实施例中，公开了用于混合速率加上基于窗口的拥塞协议的方法和系统，其控制到网络的分组传输速率并提供低排队延迟，实际上零分组丢失，多个流之间的网络资源的公平分配以及全部 链接利用率。 在一个实施例中，可以使用拥塞窗口来控制未完成比特的最大数量，可以使用传输速率来控制进入网络的分组的速率（分组起搏），基于排队延迟的速率更新可以用于控制 可以利用容忍范围内的排队延迟并尽可能减少分组丢失，并且可以使用积极的提升/优雅退避来充分利用链路容量，并且可以使用加法增加乘法减少（AIMD）速率控制来提供多个 流动。

公开(公告)号：US20130263151A1

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

申请号：US13438465

申请日：2012-04-03

申请人： Jin Li ,  Cheng Huang ,  Sudipta Sengupta ,  Christopher Broder Wilson

发明人： Jin Li ,  Cheng Huang ,  Sudipta Sengupta ,  Christopher Broder Wilson

IPC分类号： G06F9/46

CPC分类号： G06F9/5083

摘要： Described is a technology by which a consistent hashing table of bins maintains values representing nodes of a distributed system. An assignment stage uses a consistent hashing function and a selection algorithm to assign values that represent the nodes to the bins. In an independent mapping stage, a mapping mechanism deterministically maps an object identifier/key to one of the bins as a mapped-to bin.

摘要翻译： 描述了一种技术，通过该技术，一致的散列表的哈希表保持代表分布式系统的节点的值。 分配阶段使用一致的散列函数和选择算法来将表示节点的值分配给分组。 在独立的映射阶段，映射机制确定性地将对象标识符/密钥映射到一个存储区，作为映射到bin。

公开(公告)号：US08260951B2

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

申请号：US12612395

申请日：2009-11-04

申请人： Minghua Chen ,  Miroslav Ponec ,  Sudipta Sengupta ,  Jin Li ,  Philip A. Chou

发明人： Minghua Chen ,  Miroslav Ponec ,  Sudipta Sengupta ,  Jin Li ,  Philip A. Chou

IPC分类号： G06F15/16

CPC分类号： H04L67/104 ,  H04L65/80 ,  H04L67/1085

摘要： Difficulties associated with choosing advantageous network routes between server and clients are mitigated by a routing system that is devised to use many routing path sets, where respective sets comprise a number of routing paths covering all of the clients, including through other clients. A server may then apportion a data stream among all of the routing path sets. The server may also detect the performance of the computer network while sending the data stream between clients, and may adjust the apportionment of the routing path sets including the route. The clients may also be configured to operate as servers of other data streams, such as in a videoconferencing session, for example, and may be configured to send detected route performance information along with the portions of the various data streams.

摘要翻译： 通过设计为使用许多路由路径集的路由系统来减轻与服务器和客户端之间选择有利的网络路由相关联的困难，其中相应的集合包括覆盖所有客户端的多个路由路径，包括通过其他客户端。 然后，服务器可以在所有路由路径集之间分配数据流。 服务器还可以在客户端之间发送数据流时检测计算机网络的性能，并且可以调整包括路由的路由路径集合的分配。 客户端还可以被配置为例如在视频会议会话中作为其他数据流的服务器操作，并且可以被配置为发送检测到的路由性能信息以及各种数据流的部分。

公开(公告)号：US08194535B2

公开(公告)日：2012-06-05

申请号：US11141257

申请日：2005-05-31

申请人： Muralidharan S. Kodialam ,  Tirunell V. Lakshman ,  Sudipta Sengupta

发明人： Muralidharan S. Kodialam ,  Tirunell V. Lakshman ,  Sudipta Sengupta

IPC分类号： G01R31/08

CPC分类号： H04L45/12 ,  H04L45/04 ,  H04L45/24 ,  H04L47/125

摘要： In one embodiment, a method for supporting recovery from failure of a node in a network of nodes interconnected by links A set of two or more intermediate nodes (excluding the failed node) between an ingress point and an egress point is selected. Next, based on available bandwidth of the network, a non-zero fraction of the service level to route from the ingress point to each intermediate node is determined. Packets are then routed in two phases by: (1) determining one or more paths from the ingress point to each intermediate node for routing the corresponding fraction of the service level, and (2) determining one or more paths from each intermediate node to the egress point for routing the corresponding fraction of the service level.

摘要翻译： 在一个实施例中，选择用于支持通过链路互连的节点网络中的节点从在入口点和出口点之间的两个或多个中间节点（不包括故障节点）组成的恢复的方法。 接下来，基于网络的可用带宽，确定从入口点到每个中间节点路由的服务级别的非零分数。 然后，分组通过以下两个阶段路由分组：（1）确定从入口点到每个中间节点的一个或多个路径，用于路由服务级别的相应部分，以及（2）确定从每个中间节点到 出口点用于路由服务级别的相应部分。