公开(公告)号：US20090300183A1

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

申请号：US12535805

申请日：2009-08-05

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

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

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

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.

摘要翻译： 在流处理网络中操作的方法和装置执行卸载和动态资源分配，以满足预定的效用标准。 负载脱落被设想为包括允许流程处理网络中的工作流的源节点的准入控制问题。 使用原始双重方法来分解入学控制和资源分配问题。 准入控制作为推拉过程进行操作，其中源将工作流推送到流处理网络并且从网络中吸收经处理的工作流。 每个节点都维护一个虚拟队列，以解决队列积压和来自宿的积分。 流处理网络的节点维护每个工作流的影子价格，并与邻居节点共享拥塞信息。 在每个节点，资源用于工作流程，具有下游压力和处理速率的最大乘积，其中下游压力被定义为相邻节点之间的积压差异。 原始双控制器使用局部拥塞反馈迭代地调整入局速率和资源分配。 迭代控制程序进一步使用内点方法来提高收敛速度以达到最佳准入和分配决策。

公开(公告)号：US20080304516A1

公开(公告)日：2008-12-11

申请号：US11758706

申请日：2007-06-06

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

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

IPC分类号： H04J3/16

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.

摘要翻译： 在流处理网络中操作的方法和装置执行卸载和动态资源分配，以满足预定的效用标准。 负载脱落被设想为包括允许流程处理网络中的工作流的源节点的准入控制问题。 使用原始双重方法来分解入学控制和资源分配问题。 准入控制作为推拉过程进行操作，其中源将工作流推送到流处理网络并且从网络中吸收经处理的工作流。 每个节点都维护一个虚拟队列，以解决队列积压和来自宿的积分。 流处理网络的节点维护每个工作流的影子价格，并与邻居节点共享拥塞信息。 在每个节点，资源用于工作流程，具有下游压力和处理速率的最大乘积，其中下游压力被定义为相邻节点之间的积压差异。 原始双控制器使用局部拥塞反馈迭代地调整入局速率和资源分配。 迭代控制程序进一步使用内点方法来提高收敛速度以达到最佳准入和分配决策。

公开(公告)号：US20080244072A1

公开(公告)日：2008-10-02

申请号：US12132855

申请日：2008-06-04

申请人： James Andrew Broberg ,  Zhen Liu ,  Honghui Xia ,  Li Zhang

发明人： James Andrew Broberg ,  Zhen Liu ,  Honghui Xia ,  Li Zhang

IPC分类号： G06F15/16

CPC分类号： H04L47/10 ,  H04L47/25 ,  H04L47/30

摘要： A system and method for resource allocation includes, in a network having nodes and links, injecting units of flow for at least one commodity at a source corresponding to the at least one commodity. At each node, queue heights, associated with the at least one commodity, are balanced for queues associated with each of one or more outgoing paths associated with that node. An amount of commodity flow is pushed across a link toward a sink, where the amount of commodity flow is constrained by a capacity constraint. Flow that reached the sink is absorbed by draining the queues.

摘要翻译： 用于资源分配的系统和方法包括在具有节点和链路的网络中，在与所述至少一种商品相对应的源处的至少一种商品的注入单元流中。 在每个节点处，与至少一个商品相关联的队列高度对于与与该节点相关联的一个或多个输出路径中的每一个相关联的队列进行平衡。 商品流的量被推向一个靠近水槽的连接处，其中商品流的量被容量限制所约束。 到达水槽的流量通过排空排队而被吸收。

公开(公告)号：US20080172671A1

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

申请号：US11622163

申请日：2007-01-11

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

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

IPC分类号： G06F9/46

CPC分类号： G06F11/3476 ,  G06F11/3452

摘要： The present invention is based on the main ideas that different sub-intervals of a resource utilization time series are to be summarized with different granularity in the time axis, depending on the values of the series over that interval. Therefore, periods of high resource utilization are represented with higher time granularity, while periods of low resource utilization are represented with lower time granularity, the value stored can represent a function of the summarized values, such as the average or maximum value of the low resource utilization period. The captured resource utilization data is used to generate profiles, wherein the profiles summarize the historical utilization data. The profiles further capture pseudo-periodic behavior over different time scales.

摘要翻译： 本发明基于如下主要思想：资源利用时间序列的不同子时间间隔在时间轴上以不同的粒度被总结，这取决于该间隔上的序列值。 因此，高资源利用周期以较高的时间粒度表示，而资源利用率低的周期以较低的时间粒度表示，存储的值可以表示汇总值的函数，例如低资源的平均值或最大值 利用期。 捕获的资源利用率数据用于生成简档，其中概要文件概括了历史使用数据。 轮廓进一步捕获不同时间尺度的伪周期行为。

公开(公告)号：US06957357B2

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

申请号：US09920138

申请日：2001-07-31

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

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

IPC分类号： G06F1/10 ,  G06F1/04

CPC分类号： G06F1/10

摘要： A method, computer program product, and data processing system for estimating and correcting the amount of clock skew in end-to-end network timing measurements is disclosed. Measured delays are combined with their time of measurement to create ordered pairs. These ordered pairs represent points within a Cartesian plane. The convex hull of these points is determined, and an optimal line segment from the resulting polygon is selected and extrapolated to create an affine function estimating clock skew over time. The optimal line segment of the polygon is one that optimizes a selected objective function. The objective function is selected so as to be an appropriate measurement of the accuracy of the resulting linear function as an estimate of the actual clock skew.

摘要翻译： 公开了一种用于估计和校正端到端网络定时测量中的时钟偏移量的方法，计算机程序产品和数据处理系统。 测量的延迟与其测量时间相结合以创建有序对。 这些有序对表示笛卡尔平面内的点。 确定这些点的凸包，并且从所得到的多边形中选择并外推最优线段以产生估计随时间的时钟偏移的仿射函数。 多边形的最优线段是优化选定目标函数的线段。 选择目标函数，以便作为实际时钟偏差的估计，对所得到的线性函数的精度进行适当的测量。

公开(公告)号：US07894980B2

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

申请号：US11052310

申请日：2005-02-07

申请人： Zhen Liu ,  Laura Wynter ,  Li Zhang

发明人： Zhen Liu ,  Laura Wynter ,  Li Zhang

IPC分类号： G08G1/00 ,  G08G1/005 ,  G08G1/017 ,  G08G1/127

CPC分类号： G08G1/096816 ,  G08G1/0104 ,  G08G1/096827 ,  H04L47/2416 ,  H04L47/283

摘要： The present invention is a method and an apparatus for estimating real-time travel times or traffic loads (e.g., traffic flows or densities) over a transportation network based on limited real-time data. In one embodiment, a method for estimating a travel time over a transportation network comprising at least a first link and a second link includes receiving a data feed associated with a real-time traffic flow over the first link, estimating a first travel time over the first link based at least in part on the data feed, and estimating a second travel time over the second link, also based at least in part on the data feed. The method assumes that a real-time data feed is not available for the second link, and thus estimates the traffic flow over the second link based on the known traffic flow over the first link and other known data, such as historical traffic patterns and physical parameters of the transportation network.

摘要翻译： 本发明是一种用于基于有限的实时数据在运输网络上估计实时旅行时间或业务负载（例如，业务流量或密度）的方法和装置。 在一个实施例中，用于估计包括至少第一链路和第二链路的运输网络的行进时间的方法包括：接收与第一链路上的实时业务流相关联的数据馈送，估计在第一链路上的第一行进时间 至少部分地基于数据馈送，以及至少部分地基于数据馈送来估计超过第二链路的第二行进时间的第一链路。 该方法假设实时数据馈送不可用于第二链路，并且因此基于第一链路上的已知业务流和其他已知数据（诸如历史流量模式和物理上的）来估计第二链路上的业务流量 交通网络参数。

公开(公告)号：US08144590B2

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

申请号：US12132855

申请日：2008-06-04

申请人： James Andrew Broberg ,  Zhen Liu ,  Honghui Xia ,  Li Zhang

发明人： James Andrew Broberg ,  Zhen Liu ,  Honghui Xia ,  Li Zhang

IPC分类号： G01R31/08

CPC分类号： H04L47/10 ,  H04L47/25 ,  H04L47/30

摘要： A system and method for resource allocation includes, in a network having nodes and links, injecting units of flow for at least one commodity at a source corresponding to the at least one commodity. At each node, queue heights, associated with the at least one commodity, are balanced for queues associated with each of one or more outgoing paths associated with that node. An amount of commodity flow is pushed across a link toward a sink, where the amount of commodity flow is constrained by a capacity constraint. Flow that reached the sink is absorbed by draining the queues.

摘要翻译： 用于资源分配的系统和方法包括在具有节点和链路的网络中，在与所述至少一种商品相对应的源处的至少一种商品的注入单元流中。 在每个节点处，与至少一个商品相关联的队列高度对于与与该节点相关联的一个或多个输出路径中的每一个相关联的队列进行平衡。 商品流的量被推向一个靠近水槽的连接处，其中商品流的量被容量限制所约束。 到达水槽的流量通过排空排队而被吸收。

公开(公告)号：US07593353B2

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

申请号：US10800305

申请日：2004-03-13

申请人： 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.

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

公开(公告)号：US07386611B2

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

申请号：US10315335

申请日：2002-12-10

申请人： Daniel Manuel Dias ,  Richard Pervin King ,  Zhen Liu ,  Mark Steven Squillante ,  Honghui Xia ,  Shun-Zheng Yu ,  Li Zhang

发明人： Daniel Manuel Dias ,  Richard Pervin King ,  Zhen Liu ,  Mark Steven Squillante ,  Honghui Xia ,  Shun-Zheng Yu ,  Li Zhang

IPC分类号： G06F15/173

CPC分类号： H04L29/06 ,  H04L41/142 ,  H04L43/16 ,  H04L47/122 ,  H04L67/1002 ,  H04L67/1008 ,  H04L67/101 ,  H04L67/1012 ,  H04L67/1021 ,  H04L67/1023 ,  H04L67/1029 ,  H04L67/22 ,  H04L69/329 ,  H04L2029/06054

摘要： Apparatus and methods for identifying traffic patterns to web sites based on templates that characterize the arrival of traffic to the web sites are provided. Based on these templates, determinations are made as to which web sites should be co-located so as to optimize resource allocation. Specifically, web sites whose templates are complimentary, i.e. a first web site having a peak in arrival traffic at time t1 and a second web site that has a trough in arrival traffic at time t1, are designated as being candidates for co-location. In addition, the present invention uses the templates identified for the traffic patterns of web sites to determine thresholds for offloading traffic to other servers. These thresholds include a first threshold at which offloading should be performed, a second threshold that takes into consideration the lead time needed to begin offloading, and a third threshold that takes into consideration a lag time needed to stop all offloading of traffic to the other servers.

摘要翻译： 提供了基于表征网站到达流量的模板来识别网站的流量模式的装置和方法。 基于这些模板，确定哪些网站应该位于同一位置，以优化资源分配。 具体来说，其模板是免费的网站，即在时间t 1处具有到达业务峰值的第一网站和在时间t 1处具有到达业务波谷的第二网站被指定为用于共同定位的候选 。 此外，本发明使用为网站的流量模式识别的模板来确定将流量卸载到其他服务器的阈值。 这些阈值包括应该执行卸载的第一阈值，考虑到开始卸载所需的前置时间的第二阈值，以及考虑到停止对其他服务器的所有卸载流量所需的滞后时间的第三阈值 。

公开(公告)号：US07363144B2

公开(公告)日：2008-04-22

申请号：US11052309

申请日：2005-02-07

申请人： Zhen Liu ,  Laura Wynter ,  Li Zhang

发明人： Zhen Liu ,  Laura Wynter ,  Li Zhang

IPC分类号： G06F19/00

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.

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