公开(公告)号：US20090193105A1

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

申请号：US12011925

申请日：2008-01-30

申请人： Anna Charny ,  David Tsiang ,  Mohammed Ismael Tatar ,  John Bettink ,  David Getchell ,  Clarence Filsfils

发明人： Anna Charny ,  David Tsiang ,  Mohammed Ismael Tatar ,  John Bettink ,  David Getchell ,  Clarence Filsfils

IPC分类号： G06F15/173

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

摘要： In one embodiment, an apparatus generally comprises one or more input interfaces for receiving a plurality of flows, a plurality of output interfaces, and a processor operable to identify large flows and select one of the output interfaces for each of the large flows to load-balance the large flows over the output interfaces. The apparatus further includes memory for storing a list of the large flows, a pinning mechanism for pinning the large flows to the selected interfaces, and a load-balance mechanism for selecting one of the output interfaces for each of the remaining flows. A method for local placement of large flows to assist in load-balancing is also disclosed.

摘要翻译： 在一个实施例中，装置通常包括用于接收多个流的一个或多个输入接口，多个输出接口和可操作以识别大流并且为每个大流量选择一个输出接口的处理器， 平衡输出接口上的大流量。 该装置还包括用于存储大流的列表的存储器，用于将大流锁定到所选接口的钉扎机构，以及用于为每个剩余流选择一个输出接口的负载平衡机构。 还公开了用于局部放置大流量以辅助负载平衡的方法。

公开(公告)号：US07418493B1

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

申请号：US10262296

申请日：2002-09-30

申请人： Anna Charny ,  Hani El-Sakkout ,  Barry Richards

发明人： Anna Charny ,  Hani El-Sakkout ,  Barry Richards

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

CPC分类号： H04L47/10 ,  H04L45/50 ,  H04L47/125

摘要： Systems and methods for estimating aggregate bandwidths of primary traffic flows are provided. Tighter upper bounds on aggregate bandwidths for arbitrary combinations of primary traffic flows may be computed. These tighter bounds are highly useful in configuring backup tunnels to protect a node in the event of failure in that the total backup bandwidth burden on individual links may be determined more accurately to permit optimal use of available backup bandwidth capacity.

摘要翻译： 提供了用于估计主要业务流的聚合带宽的系统和方法。 可以计算主要业务流的任意组合的聚合带宽的更紧密的上限。 这些更紧密的边界在配置备份隧道以在发生故障的情况下保护节点非常有用，因为可以更精确地确定各个链路上的总备份带宽负担，以允许最佳使用可用的备份带宽容量。

公开(公告)号：US07231425B1

公开(公告)日：2007-06-12

申请号：US10243436

申请日：2002-09-13

申请人： Anna Charny ,  Robert Olsen

发明人： Anna Charny ,  Robert Olsen

IPC分类号： G06F15/16

CPC分类号： H04L47/10 ,  H04L47/22

摘要： A rate-based scheduling system and method are disclosed. The rate-based system generally includes a first scheduler operable to limit the maximum rates at each of the plurality of queues. The first scheduler is configured as a work conserving scheduler shaped at an aggregate rate of active queues of the plurality of queues. The system further includes a second scheduler operable to provide a minimum rate to each of the plurality of queues and a rate controller configured to modulate the rate of at least one of the first and second schedulers.

摘要翻译： 公开了一种基于速率的调度系统和方法。 基于速率的系统通常包括可操作以限制多个队列中的每一个的最大速率的第一调度器。 第一调度器被配置为以多个队列中的活动队列的聚合速率成形的工作保存调度器。 所述系统还包括第二调度器，可操作以向所述多个队列中的每一个提供最小速率;以及速率控制器，被配置为调制所述第一和第二调度器中的至少一个调度器的速率。

公开(公告)号：US20060153243A1

公开(公告)日：2006-07-13

申请号：US11022220

申请日：2004-12-23

申请人： Doron Shoham ,  Christopher Kappler ,  Anna Charny ,  Earl Cohen ,  Robert Olsen

发明人： Doron Shoham ,  Christopher Kappler ,  Anna Charny ,  Earl Cohen ,  Robert Olsen

IPC分类号： H04J3/06

CPC分类号： H04L47/564 ,  H04L47/50

摘要： Eligible entries are scheduled using an approximated finish delay identified for an entry based on an associated speed group. One implementation maintains schedule entries, each respectively associated with a start time and a speed group. Each speed group is associated with an approximated finish delay. An approximated earliest finishing entry from the eligible schedule entries is determined that has an earliest approximated finish time, with the approximated finish time of an entry being determined based on the entry's start time and the approximated finish delay of the associated speed group. The scheduled action corresponding to the approximated earliest finishing entry is then typically performed. The action performed may, for example, correspond to the forwarding of one or more packets, an amount of processing associated with a process or thread, or any activity associated with an item.

公开(公告)号：US06978394B1

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

申请号：US10080956

申请日：2002-02-22

申请人： Anna Charny ,  Robert Goguen ,  Carol Iturralde

发明人： Anna Charny ,  Robert Goguen ,  Carol Iturralde

IPC分类号： G06F11/00

CPC分类号： H04L45/00 ,  H04L45/125 ,  H04L45/24 ,  H04L45/28

摘要： Load balancing enables the use of linear programming techniques to reduce the complexity of computing backup tunnel placement for guaranteed bandwidth protection. The ability to load balance among multiple backup tunnels transforms the placement problem into one that may be characterized as a series of linear constraints usable as input to a linear programming procedure such as the simplex method. Each node may compute its own backup tunnels and signal the tunnels to its neighbors with zero bandwidth to allow implicit sharing of backup bandwidth.

摘要翻译： 负载平衡可以使用线性规划技术来减少计算备份隧道布局的复杂性，以保证带宽保护。 在多个备用隧道之间进行负载平衡的能力将放置问题转换为可以表征为一系列可用作线性规划过程（如单纯形法）的输入的线性约束的问题。 每个节点可以计算其自己的备份隧道，并以0带宽将隧道信号发送给其邻居，以允许隐式共享备份带宽。

公开(公告)号：US06778492B2

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

申请号：US10052665

申请日：2002-01-17

申请人： Anna Charny ,  Robert James Goguen ,  Carol Iturralde

发明人： Anna Charny ,  Robert James Goguen ,  Carol Iturralde

IPC分类号： H04L1228

CPC分类号： H04L45/00 ,  H04L45/24 ,  H04L45/28 ,  H04L45/50

摘要： Load balancing among fast reroute backup tunnels in a label switched network is achieved. M backup tunnels may be used to protect N parallel paths. A single backup tunnel may protect multiple parallel paths, saving on utilization of network resources such as router state and signaling information. A single path may be protected by multiple backup tunnels, assuring that bandwidth guarantees are met under failure conditions even when no one backup tunnel with sufficient bandwidth may be found. A packing algorithm is used to associate individual label switched paths (LSPs) with individual backup tunnels. If an LSP cannot be assigned to a backup tunnel, it may be either rejected, or additional bandwidth is allocated to existing backup tunnels, or a new backup tunnel is established.

摘要翻译： 实现标签交换网络中快速重路由备份隧道之间的负载分担。 M个备用隧道可用于保护N条并行路径。 单个备份隧道可以保护多个并行路径，节省了路由器状态和信令信息等网络资源的利用。 单个路径可能受到多个备份隧道的保护，即使没有发现具有足够带宽的备份隧道，也能确保在故障条件下满足带宽保证。 使用打包算法将各个标签交换路径（LSP）与各个备份隧道相关联。 如果LSP不能分配给备份隧道，则可能会被拒绝，或者将其他带宽分配给现有的备份隧道，或建立新的备份隧道。

公开(公告)号：US06337851B1

公开(公告)日：2002-01-08

申请号：US09629727

申请日：2000-07-31

申请人： Anna Charny ,  Wing Cheung ,  Peter Roman ,  Robert Thomas

发明人： Anna Charny ,  Wing Cheung ,  Peter Roman ,  Robert Thomas

IPC分类号： H04L100

CPC分类号： H04L12/5602 ,  H04L2012/5616 ,  H04L2012/5619 ,  H04L2012/5679 ,  H04Q11/0478

摘要： A method of scheduling a plurality of data flows in a shared resource in a computer system, each of the data flows containing a plurality of data cells including the steps of providing a scheduler in the shared resource, initializing the scheduler to receive the plurality of data flows, receiving a first data flow in the scheduler, said first data flow having a first flow rate, receiving a second data flow in the scheduler, said second data flow having a second flow rate, scheduling, by the scheduler, the first data flow and the second data flow such that the first flow rate and the second flow rate are less than an available bandwidth in the shared resource and a relative error is minimized between an actual scheduling time and an ideal scheduling time on a per cell basis, and repeating the steps of receiving and scheduling.

摘要翻译： 一种在计算机系统中的共享资源中调度多个数据流的方法，每个数据流包含多个数据单元，包括以下步骤：在共享资源中提供调度器，初始化调度器以接收多个数据 流，在调度器中接收第一数据流，所述第一数据流具有第一流速，接收调度器中的第二数据流，所述第二数据流具有第二流速，由调度器调度第一数据流 以及第二数据流，使得第一流量和第二流量小于共享资源中的可用带宽，并且在每个小区的基础上在实际调度时间和理想调度时间之间将相对误差最小化，并重复 接收和调度的步骤。

公开(公告)号：US5968128A

公开(公告)日：1999-10-19

申请号：US845336

申请日：1997-04-25

申请人： Anthony G. Lauck ,  Anna Charny ,  Kadangode K. Ramakrishnan

发明人： Anthony G. Lauck ,  Anna Charny ,  Kadangode K. Ramakrishnan

IPC分类号： G06F15/16 ,  G06F15/177 ,  H04L12/56 ,  H04Q11/04 ,  G06F13/00

CPC分类号： H04L12/5602 ,  H04L47/10 ,  H04L47/263 ,  H04L47/39 ,  H04Q11/0478 ,  H04L2012/5619 ,  H04L2012/563 ,  H04L2012/5632 ,  H04L2012/5634 ,  Y02B60/31

摘要： The rate based end system may provide feasible transmission rates for end source stations. As an extension to the rate based end to end system, there is disclosed a hybrid link by link flow control system. The link by link control system is built upon the end to end, rate based traffic control system. The link by link system utilizes bandwidth un accounted for by the end to end system. The link by link system uses feasible transmission rates obtained by the end to end system to determine the size of the buffers required for overbooking and for updating credit information to sustain the calculated rate.

摘要翻译： 基于速率的终端系统可以为终端源站提供可行的传输速率。 作为基于速率的端到端系统的扩展，公开了一种通过链路流控制系统的混合链路。 链路控制系统的链路建立在端到端，基于速率的流量控制系统上。 链路系统利用端到端系统占用的带宽。 通过链路系统的链路使用端对端系统获得的可行的传输速率来确定超量预定所需的缓冲区的大小以及更新信用信息以维持计算的速率。

公开(公告)号：US5781531A

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

申请号：US578932

申请日：1995-12-27

申请人： Anna Charny

发明人： Anna Charny

IPC分类号： G06F13/00 ,  G06F9/46 ,  G06F9/50 ,  H04L12/56 ,  H04Q11/04 ,  H04J3/02

CPC分类号： H04L12/5602 ,  H04L47/10 ,  H04Q11/0478 ,  H04L2012/5616 ,  H04L2012/5619 ,  H04L2012/5679

摘要： A novel scheduling method is provided which may be used for rate-based scheduling (e.g., for scheduling flows at some assigned rates in a computer network) or for weighted fair sharing of a common resource (e.g., scheduling weighted jobs in a processor). The method is based on hierarchical application of Relative Error (RE) scheduling. The present method of a Hierarchical RE Scheme (HRE) with complexity O(log(N)), where N is the maximum number of jobs supported by the scheduler, is provided.

摘要翻译： 提供了一种新颖的调度方法，其可用于基于速率的调度（例如，用于以计算机网络中的某些分配速率调度流）或用于公共资源的加权公平共享（例如，在处理器中调度加权作业）。 该方法基于相对误差（RE）调度的分层应用。 提供了具有复杂度O（log（N））的分层RE方案（HRE）的当前方法，其中N是由调度器支持的最大作业数。

公开(公告)号：US5745697A

公开(公告)日：1998-04-28

申请号：US622801

申请日：1996-03-27

申请人： Anna Charny ,  K. K. Ramakrishnan

发明人： Anna Charny ,  K. K. Ramakrishnan

IPC分类号： H04L12/56 ,  G06F13/00

CPC分类号： H04L12/5602 ,  H04L47/10 ,  H04L47/16 ,  H04L47/263 ,  H04L2012/5635

摘要： A computational method and apparatus allocates transmission rate to source end nodes, and both reduces the computational complexity, and reduces the state information which must be retained concerning each VC, without significantly degrading convergence properties for the network. Also, the computational method is useful with either interval based or proportional schemes of flow control. A plurality of virtual circuits is established between source end stations and destination end stations, the plurality of virtual circuits passing through an intermediate node. The source end stations transmit data packets at a plurality of discrete transmission rates. The intermediate node counts the number of virtual circuits using each of the discrete transmission rates. The intermediate node maintains an indication that a select virtual circuit has been counted in the step above, and does not count the virtual circuit more than once during a switch time interval. The intermediate node, responsive to counting the number of virtual circuits using each of the discrete transmission rates, calculates a rate allocation value for the plurality of virtual circuits, the calculation is done periodically during the switch time interval. The rate allocation value is written into the field of the data packet in order to signal to the source end station, and any intervening intermediate node, the rate allocation value calculated above.

摘要翻译： 一种计算方法和装置为源端节点分配传输速率，并且都降低了计算复杂度，并且减少了关于每个VC必须保留的状态信息，而没有显着降低网络的收敛性质。 此外，计算方法对于基于间隔的或流量控制的比例方案是有用的。 在源端站和目的端站之间建立多个虚拟电路，多个虚拟电路通过中间节点。 源端站以多个离散传输速率发送数据分组。 中间节点使用每个离散传输速率对虚拟电路的数量进行计数。 中间节点保持在上述步骤中已经计数了选择虚拟电路的指示，并且在切换时间间隔期间不再多次计数虚拟电路。 中间节点响应于使用每个离散传输速率对虚拟电路的数量进行计数，计算多个虚拟电路的速率分配值，在切换时间间隔期间周期性地进行计算。 速率分配值被写入数据分组的字段，以便向源终端发送信号，并且任何中间节点，上面计算出的速率分配值。