公开(公告)号：US07826365B2

公开(公告)日：2010-11-02

申请号：US11519764

申请日：2006-09-12

申请人： Ao (Kevin) Tang ,  Zhen Liu ,  Honghui (Cathy) Xia ,  Li Zhang

发明人： Ao (Kevin) Tang ,  Zhen Liu ,  Honghui (Cathy) Xia ,  Li Zhang

IPC分类号： H04L1/00

CPC分类号： H04L47/70

摘要： Resource allocations in stream data processing systems are performed to allocate the resources in a cost-effective manner by formulating the resource allocation problem as a linear program. For a problem with a single output, a backward algorithm or method is used that produces an optimal solution in linear time. For a problem with multiple outputs and the network has a tree structure, a backward shrink algorithm or method is used to provide an optimal solution in linear time. These algorithms are fully distributed, they require only local exchange of parameters between neighboring nodes, and are adaptive to the dynamic changes in network conditions and flow rate fluctuations.

摘要翻译： 执行流数据处理系统中的资源分配，通过以资源分配问题作为线性程序，以成本有效的方式分配资源。 对于单个输出的问题，使用向后算法或方法，其产生线性时间的最优解。 对于多个输出的问题，网络具有树结构，使用向后收缩算法或方法来提供线性时间的最优解。 这些算法是完全分布的，它们只需要相邻节点之间的本地参数交换，并且适应网络条件和流量波动的动态变化。

公开(公告)号：US20080062886A1

公开(公告)日：2008-03-13

申请号：US11519764

申请日：2006-09-12

申请人： Ao (Kevin) Tang ,  Zhen Liu ,  Honghui (Cathy) Xia ,  Li Zhang

发明人： Ao (Kevin) Tang ,  Zhen Liu ,  Honghui (Cathy) Xia ,  Li Zhang

IPC分类号： H04J1/16

CPC分类号： H04L47/70

摘要： Resource allocations in stream data processing systems are performed to allocate the resources in a cost-effective manner by formulating the resource allocation problem as a linear program. For a problem with a single output, a backward algorithm or method is used that produces an optimal solution in linear time. For a problem with multiple outputs and the network has a tree structure, a backward shrink algorithm or method is used to provide an optimal solution in linear time. These algorithms are fully distributed, they require only local exchange of parameters between neighboring nodes, and are adaptive to the dynamic changes in network conditions and flow rate fluctuations.

摘要翻译： 执行流数据处理系统中的资源分配，通过以资源分配问题作为线性程序，以成本有效的方式分配资源。 对于单个输出的问题，使用向后算法或方法，其产生线性时间的最优解。 对于多个输出的问题，网络具有树结构，使用向后收缩算法或方法来提供线性时间的最优解。 这些算法是完全分布的，它们只需要相邻节点之间的本地参数交换，并且适应网络条件和流量波动的动态变化。

公开(公告)号：US07739099B2

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

申请号：US11315692

申请日：2005-12-22

申请人： Zhen Liu ,  Honghui (Cathy) Xia ,  Fan Zhang ,  Li Zhang

发明人： Zhen Liu ,  Honghui (Cathy) Xia ,  Fan Zhang ,  Li Zhang

IPC分类号： G06F7/60 ,  G06F9/45 ,  G06F11/30 ,  G06F15/173 ,  G06F9/44

CPC分类号： G06Q10/06 ,  Y02P90/86

摘要： A system and method for performance modeling for an information technology (IT) system having a server(s) for performing a number of types of transactions includes receiving data for system topology and transaction flows and receiving performance measurement data for the IT system. The measurement data is clustered into multiple regimes based on similarities. Service demand and network delay parameters may be inferred based on clustered data.

摘要翻译： 用于具有用于执行多种类型的事务的服务器的信息技术（IT）系统的性能建模的系统和方法包括接收用于系统拓扑和事务流的数据以及接收IT系统的性能测量数据。 基于相似度将测量数据聚类成多个体系。 服务需求和网络延迟参数可以基于聚类数据来推断。

公开(公告)号：US08040824B2

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

申请号：US12502714

申请日：2009-07-14

申请人： Zhen Liu ,  Anton Riabov ,  Li Zhang

发明人： Zhen Liu ,  Anton Riabov ,  Li Zhang

IPC分类号： H04L12/28

CPC分类号： H04L45/48 ,  H04L12/1881 ,  H04L45/16

摘要： A method for constructing an overlay multicast tree to deliver data from a source to an identified group of nodes is provided in which a plurality of nodes are identified and mapped into multidimensional Euclidean space. A geometric region is constructing having a size that is the minimum size necessary to contain the source and all the nodes. Once constructed, a tree is created beginning at the source and including all of the nodes within the geometric region.

摘要翻译： 提供了一种用于构建覆盖多播树以将数据从源传送到所识别的节点组的方法，其中多个节点被识别并映射到多维欧几里德空间中。 一个几何区域正在构造，其大小是包含源和所有节点所需的最小大小。 一旦构造，从源头创建树，并且包括几何区域内的所有节点。

公开(公告)号：US07889651B2

公开(公告)日：2011-02-15

申请号：US11758706

申请日：2007-06-06

申请人： Hanhua Feng ,  Zhen Liu ,  Honghui Xia ,  Li Zhang

发明人： Hanhua Feng ,  Zhen Liu ,  Honghui Xia ,  Li Zhang

IPC分类号： G01R31/08

CPC分类号： G06F9/5066 ,  G06F9/5038

摘要： Methods and apparatus operating in a stream processing network perform load shedding and dynamic resource allocation so as to meet a pre-determined utility criterion. Load shedding is envisioned as an admission control problem encompassing source nodes admitting workflows into the stream processing network. A primal-dual approach is used to decompose the admission control and resource allocation problems. The admission control operates as a push-and-pull process with sources pushing workflows into the stream processing network and sinks pulling processed workflows from the network. A virtual queue is maintained at each node to account for both queue backlogs and credits from sinks. Nodes of the stream processing network maintain shadow prices for each of the workflows and share congestion information with neighbor nodes. At each node, resources are devoted to the workflow with the maximum product of downstream pressure and processing rate, where the downstream pressure is defined as the backlog difference between neighbor nodes. The primal-dual controller iteratively adjusts the admission rates and resource allocation using local congestion feedback. The iterative controlling procedure further uses an interior-point method to improve the speed of convergence towards optimal admission and allocation decisions.

公开(公告)号：US07626917B2

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

申请号：US10865064

申请日：2004-06-10

申请人： Wuqin Lin ,  Zhen Liu ,  Cathy Honghui Xia ,  Li Zhang

发明人： Wuqin Lin ,  Zhen Liu ,  Cathy Honghui Xia ,  Li Zhang

IPC分类号： H04J11/00 ,  G06F9/44 ,  G06F9/45

CPC分类号： G06F9/50 ,  G06F9/5061

摘要： Techniques are provided for determining a capacity allocation in a multi-tiered computing system. In one aspect of the invention, a technique for designing capacity allocation for a multi-tiered computing system, each tier of the computing system having one or more computing devices (e.g., servers), comprises the following steps/operations. Input parameters relating to capacity allocation are obtained. A capacity allocation is computed based on at least a portion of the input parameters, the capacity allocation being computable such that one or more end-to-end performance measures are substantially satisfied for multiple service classes. The capacity allocation computation may minimize a cost function. The capacity allocation computation may also satisfy one or more mean delay guarantees for the multiple service classes, one or more tail distribution guarantees for the multiple service classes, or both one or more mean delay guarantees and one or more tail distribution guarantees for the multiple service classes.

摘要翻译： 提供了用于确定多层计算系统中的容量分配的技术。 在本发明的一个方面，一种用于设计多层计算系统的容量分配的技术，具有一个或多个计算设备（例如，服务器）的计算系统的每个层包括以下步骤/操作。 获得与容量分配有关的输入参数。 基于输入参数的至少一部分来计算容量分配，所述容量分配是可计算的，使得对于多个服务类基本上满足一个或多个端到端性能测量。 容量分配计算可以最小化成本函数。 容量分配计算还可以满足多个服务类别的一个或多个平均延迟保证，多个服务类别的一个或多个尾部分配保证，或一个或多个平均延迟保证以及用于多个服务的一个或多个尾部分配保证 课程

公开(公告)号：US20090268733A1

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

申请号：US12502714

申请日：2009-07-14

申请人： Zhen Liu ,  Anton Riabov ,  Li Zhang

发明人： Zhen Liu ,  Anton Riabov ,  Li Zhang

IPC分类号： H04L12/56

CPC分类号： H04L45/48 ,  H04L12/1881 ,  H04L45/16

摘要： A method for constructing an overlay multicast tree to deliver data from a source to an identified group of nodes is provided in which a plurality of nodes are identified and mapped into multidimensional Euclidean space. A geometric region is constructing having a size that is the minimum size necessary to contain the source and all the nodes. Once constructed, a tree is created beginning at the source and including all of the nodes within the geometric region.

摘要翻译： 提供了一种用于构建覆盖多播树以将数据从源传送到所识别的节点组的方法，其中多个节点被识别并映射到多维欧几里德空间中。 一个几何区域正在构造，其大小是包含源和所有节点所需的最小大小。 一旦构造，从源头创建树，并且包括几何区域内的所有节点。

公开(公告)号：US20080195447A1

公开(公告)日：2008-08-14

申请号：US11673118

申请日：2007-02-09

申请人： Eric Bouillet ,  Zhen Liu ,  Dimitrios Pendarakis ,  Li Zhang

发明人： Eric Bouillet ,  Zhen Liu ,  Dimitrios Pendarakis ,  Li Zhang

IPC分类号： G05B19/418 ,  G06F9/46

CPC分类号： G06F9/5061 ,  G06Q10/0631 ,  G06Q10/06315 ,  G06Q30/0202

摘要： A system and method for capacity sizing in a computer device or system includes determining one or more classes of operations based on at least one of historical computational usage and predicted usage for a system. Based on the one or more classes of operations, at least one capacity target is set based on the computational usage for each class such that computational capacity is maintained at a set level over a given time period and the set level satisfies at least one usage criterion over the given time period.

摘要翻译： 一种用于计算机设备或系统中的容量大小化的系统和方法包括基于系统的历史计算使用和预测使用中的至少一个来确定一个或多个类别的操作。 基于一个或多个类别的操作，基于每个类的计算使用来设置至少一个容量目标，使得计算能力在给定时间段内保持在设定电平，并且所述设定电平满足至少一个使用准则 在给定的时间段内。

公开(公告)号：US20080170592A1

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

申请号：US11622177

申请日：2007-01-11

申请人： Michel H.T. Hack ,  Zhen Liu ,  Ahmed A. Sobeih ,  Li Zhang

发明人： Michel H.T. Hack ,  Zhen Liu ,  Ahmed A. Sobeih ,  Li Zhang

IPC分类号： H04J3/06

CPC分类号： H04J3/0641 ,  H04J3/0664 ,  H04J3/0676

摘要： Disclosed are a method of and a system for synchronizing clocks in a coordinated network of computers including a multitude of processing nodes, each of the nodes having a clock and one or more neighbor nodes. The method comprises the steps of electing one of the nodes as a correct leader node; and each of the non-leader nodes adjusting its clock rate, based on messages exchanged with neighbor nodes, to remain synchronized with the clock of said correct leader node. In a preferred embodiment, the adjusting step includes the step of each of the non-correct leader nodes using a weight assignment mechanism that gives neighbor nodes that are closer to the leader node more effect on the clock adjustment than those nodes that are further away from the correct leader node.

摘要翻译： 公开了一种用于在包括多个处理节点的计算机的协调网络中同步时钟的方法和系统，每个节点具有时钟和一个或多个相邻节点。 该方法包括以下步骤：将节点中的一个选为正确的前导节点; 并且每个非前导节点基于与邻居节点交换的消息来调整其时钟速率，以与所述正确的前导节点的时钟保持同步。 在优选实施例中，调整步骤包括使用加权分配机制的每个非正确的前导节点的步骤，该加权分配机制给予距离前导节点更靠近时钟调整的相邻节点，而不是远离更远的节点 正确的领导节点。

公开(公告)号：US20080147307A1

公开(公告)日：2008-06-19

申请号：US12038559

申请日：2008-02-27

申请人： ZHEN LIU ,  Laura Wynter ,  Li Zhang

发明人： ZHEN LIU ,  Laura Wynter ,  Li Zhang

IPC分类号： G08G1/01

CPC分类号： G08G1/123

摘要： The present invention is a method and an apparatus for predicting future travel times over a transportation network. In one embodiment, a method for predicting future travel times over a transportation network includes receiving a data point indicating a real-time volume of traffic on the link at a given time and updating a template representative of an observed traffic pattern on the link in accordance with the received data point. A future travel time over the link can then be estimated in accordance with the updated template. Thus, the template is able to adapt to dynamically changing traffic patterns, taking these changing traffic patterns into account when making predictions of future traffic patterns.

摘要翻译： 本发明是用于预测运输网络上的未来旅行时间的方法和装置。 在一个实施例中，用于预测运输网络上的未来旅行时间的方法包括在给定时间接收指示链路上的实时流量的数据点，并且根据链路更新表示链路上观察到的业务模式的模板 与收到的数据点。 然后可以根据更新的模板来估计链接上的未来旅行时间。 因此，模板能够适应动态变化的流量模式，在对未来流量模式进行预测时考虑到这些变化的流量模式。