公开(公告)号：US6035333A

公开(公告)日：2000-03-07

申请号：US977252

申请日：1997-11-24

申请人： Clark Debs Jeffries ,  Anoop Ghanwani ,  Gerald Arnold Marin ,  Ken Van Vu

发明人： Clark Debs Jeffries ,  Anoop Ghanwani ,  Gerald Arnold Marin ,  Ken Van Vu

IPC分类号： H04L12/56 ,  G06F15/173

CPC分类号： H04L47/28 ,  H04L47/10 ,  H04L47/12 ,  H04L47/13

摘要： A bin packing algorithm is employed to schedule computer network activities, such as pause times required for operation of an Ethernet network which implements existing IEEE 802.3x standards. In such a network, any node in the network can control the flow of traffic from upstream stations in order to avoid congestion at the flow-controlling node. Upon sensing congestion, the flow-controlling node determines how long each upstream node contributing to the congestion should pause transmission over the next control interval. In accordance with the invention, the pause times are scheduled or staggered by using the bin packing algorithm to sort the sources into one or more bins. One required bin property is that there is no overlap in pause times for the sources within a particular bin. Another required bin property is that the sum of the pause times within a bin can be no greater than the length of the control interval. In a preferred embodiment, the calculated pause times are separated into different groups having different number ranges and no more than one pause time is selected from any particular group for packing into a given bin.

摘要翻译： 采用bin打包算法来调度计算机网络活动，例如实现现有IEEE 802.3x标准的以太网的操作所需的暂停时间。 在这种网络中，网络中的任何节点可以控制来自上游站的业务流，以避免流控制节点处的拥塞。 在感测到拥塞时，流控制节点确定每个有助于拥塞的上游节点在暂停下一个控制间隔时间内的传输时间。 根据本发明，通过使用二进制打包算法来排列或交错暂停时间，以将源排列成一个或多个仓。 一个必需的bin属性是在特定仓中的源的暂停时间没有重叠。 另一个所需的bin属性是bin内暂停时间的总和可以不大于控制间隔的长度。 在优选实施例中，将计算的暂停时间分成具有不同数量范围的不同组，并且从用于打包到给定仓中的任何特定组中选择不超过一个暂停时间。

公开(公告)号：US06633585B1

公开(公告)日：2003-10-14

申请号：US09374349

申请日：1999-08-13

申请人： Anoop Ghanwani ,  Metin Aydemir ,  Clark Debs Jeffries ,  Gerald Arnold Marin ,  Norman Clark Strole ,  Ken Van Vu

发明人： Anoop Ghanwani ,  Metin Aydemir ,  Clark Debs Jeffries ,  Gerald Arnold Marin ,  Norman Clark Strole ,  Ken Van Vu

IPC分类号： H04J322

CPC分类号： H04L12/5601 ,  H04L2012/561 ,  H04L2012/5617 ,  H04L2012/5635 ,  H04L2012/5636

摘要： A method and system within a telecommunications network for allocating available bandwidth among a plurality of sessions that share a common data link. First, a repeating unit time interval is designated for conducting the plurality of sessions. Next, the input flow rate from the source node of each of the sessions into the common data link is monitored. Thereafter, a target flow rate is computed and assigned to each of the sessions. The sum of the target flow rates is equal to the available bandwidth of the common data link. Finally, for each of the sessions in which the monitored input flow rate exceeds the assigned target flow rate, the source node is dynamically paused during each repeating unit time interval, such that the monitored input flow rate conforms to the assigned target flow rate for each of the sessions.

摘要翻译： 一种用于在共享公共数据链路的多个会话之间分配可用带宽的电信网络内的方法和系统。 首先，指定进行多个会话的重复单位时间间隔。 接下来，监视从每个会话的源节点到公共数据链路的输入流速。 此后，计算目标流量并将其分配给每个会话。 目标流量的总和等于公共数据链路的可用带宽。 最后，对于监视的输入流量超过分配的目标流量的每个会话，源节点在每个重复单位时间间隔期间被动态地暂停，使得所监视的输入流量符合每个 的会话。

公开(公告)号：US06185187B2

公开(公告)日：2001-02-06

申请号：US08988014

申请日：1997-12-10

申请人： Anoop Ghanwani ,  Gerald Arnold Marin ,  Ken Van Vu

发明人： Anoop Ghanwani ,  Gerald Arnold Marin ,  Ken Van Vu

IPC分类号： H04J314

CPC分类号： H04L47/30 ,  H04L47/10 ,  H04L47/29 ,  H04L2012/5635 ,  H04L2012/5682 ,  H04Q11/0478

摘要： A data transfer flow control system includes a plurality of nodes or switches in a network, which are interconnected by transmission links. Resource management cells are transmitted along with data cells in information transfer sessions. As the amount of session traffic at any node increases, the level of occupancy of the buffers for that node correspondingly increases to temporarily store overflow data. At every network node, a “fair share” cell rate is determined for each output transmission link. Whenever the current cell rate (CCR) of any session exceeds the fair share cell rate for the output link at a node, the buffer occupancy threshold values for setting congestion indication fields in the resource management cells are adjusted downwardly such that a lower threshold buffer occupancy will effect a traffic congestion setting for that session.

摘要翻译： 数据传输流控制系统包括通过传输链路互连的网络中的多个节点或交换机。 资源管理单元与信息传输会话中的数据单元一起传输。 随着任何节点处的会话流量的增加，该节点的缓冲器的占用水平相应地增加以临时存储溢出数据。 在每个网络节点，为每个输出传输链路确定“公平共享”信元速率。 每当任何会话的当前信元速率（CCR）超过节点处的输出链路的公平共享信元速率时，用于设置资源管理信元中的拥塞指示字段的缓冲器占用阈值被向下调整，使得较低的阈值缓冲器占用 将影响该会话的流量拥塞设置。

公开(公告)号：US5909443A

公开(公告)日：1999-06-01

申请号：US780149

申请日：1997-01-03

申请人： Aline Fichou ,  Serge Fdida ,  Claude Galand ,  Gerald Arnold Marin ,  Raif O. Onvural ,  Ken Van Vu

发明人： Aline Fichou ,  Serge Fdida ,  Claude Galand ,  Gerald Arnold Marin ,  Raif O. Onvural ,  Ken Van Vu

IPC分类号： H04L12/56 ,  H04Q11/04 ,  H04L12/26

CPC分类号： H04Q11/0478 ,  H04L2012/5629 ,  H04L2012/5635

摘要： An explicit rate algorithm is disclosed for use in an end-to-end closed loop flow control algorithm for an ATM network which carries at least constant bit rate (CBR) traffic, variable bit rate (VBR) traffic and adjustable bit rate (ABR) traffic. The algorithm determines how much additional bandwidth is available for ABR traffic on an output link from a node and produces an explicit rate variable that can be forwarded to a source for the ABR traffic. Both the maximum and minimum bandwidths already reserved for all connections on the output link are determined. A single reserved bandwidth value is chosen within the range defined by the maximum and minimum reserved bandwidth values. The current utilization of the ABR input buffer for the node is also determined. The explicit rate variable is generated as a function of the link capacity, the reserved bandwidth value and the current utilization of the ABR input buffer. The explicit rate variable is written into a resource management cell which is routed through the network to the ABR traffic source. The explicit rate variable is intended to change the input rate of the ABR source to utilize more of the ABR input buffer.

摘要翻译： 公开了一种用于ATM网络的端到端闭环流量控制算法的显式速率算法，该算法至少承载恒定比特率（CBR）流量，可变比特率（VBR）流量和可调比特率（ABR） 交通。 该算法确定来自节点的输出链路上的ABR流量可用的附加带宽多少，并产生可以转发到ABR流量的源的显式速率变量。 已经为输出链路上的所有连接预留的最大和最小带宽都被确定。 在由最大和最小保留带宽值定义的范围内选择单个保留带宽值。 还确定了节点的ABR输入缓冲区的当前利用率。 显式速率变量根据链路容量，保留带宽值和ABR输入缓冲区的当前利用率生成。 显式速率变量被写入通过网络路由到ABR流量源的资源管理单元。 显式速率变量旨在改变ABR源的输入速率以利用更多的ABR输入缓冲器。

公开(公告)号：US06400686B1

公开(公告)日：2002-06-04

申请号：US09585830

申请日：2000-06-01

申请人： Anoop Ghanwani ,  Brad Alan Makrucki ,  Ken Van Vu

发明人： Anoop Ghanwani ,  Brad Alan Makrucki ,  Ken Van Vu

IPC分类号： H04J116

CPC分类号： H04L47/263 ,  H04L47/22 ,  H04L47/28 ,  Y02D50/10

摘要： A data transfer flow control system for a packet communications system includes a plurality of nodes interconnected by transmission links. The rate at which a sender node transmits information to a destination node in a network is modified in accordance with congestion information returned to the sender node from nodes along the path of the transmission or from the information receiver. The rate change for information being sent from the sender node is modified based upon the amount of elapsed time occurring since the last rate change of the same type. In first and second examples, the rate change is implemented in accordance with exponential and linear relationships, respectively, between the modified flow rate and the elapsed time since the last rate change.

摘要翻译： 用于分组通信系统的数据传输流控制系统包括通过传输链路互连的多个节点。 发送方节点向网络中的目的地节点发送信息的速率根据从发送路径的节点或从信息接收机返回给发送方节点的拥塞信息进行修改。 基于从相同类型的上一次速率变化以来发生的经过时间量，修改从发送者节点发送的信息的速率变化。 在第一和第二示例中，速率变化分别根据改变的流量与上一次速率变化之后的经过时间之间的指数和线性关系来实现。

公开(公告)号：US6075769A

公开(公告)日：2000-06-13

申请号：US978831

申请日：1997-11-26

申请人： Anoop Ghanwani ,  Brad Alan Makrucki ,  Ken Van Vu

发明人： Anoop Ghanwani ,  Brad Alan Makrucki ,  Ken Van Vu

IPC分类号： G01R31/08 ,  G06F15/16 ,  H04J1/16 ,  H04J3/14 ,  H04L1/00

CPC分类号： H04L47/263 ,  H04L47/22 ,  H04L47/28 ,  Y02B60/31

摘要： A data transfer flow control system for a packet communications system includes a plurality of nodes interconnected by transmission links. The rate at which a sender node transmits information to a destination node in a network is modified in accordance with congestion information returned to the sender node from nodes along the path of the transmission or from the information receiver. The rate change for information being sent from the sender node is modified based upon the amount of elapsed time occurring since the last rate change of the same type. In first and second examples, the rate change is implemented in accordance with exponential and linear relationships, respectively, between the modified flow rate and the elapsed time since the last rate change.

公开(公告)号：US06587436B1

公开(公告)日：2003-07-01

申请号：US08977220

申请日：1997-11-24

申请人： Ken Van Vu ,  Anoop Ghanwani ,  Brad Alan Makrucki

发明人： Ken Van Vu ,  Anoop Ghanwani ,  Brad Alan Makrucki

IPC分类号： H04L1228

CPC分类号： H04L12/5602 ,  H04L47/26 ,  H04L47/263 ,  H04L2012/5631

摘要： A data transfer flow control system for a packet ATM communications system includes a plurality of nodes interconnected by transmission links. Available bandwidth allocation for data packets or cells is improved by defining a Nrm parameter to be the product of an allowable cell rate and a sampling period. Nrm is related to the number of data cells being transmitted between resource management cells in a transmission session, and is set to a number that is independent of round trip times between source and destination nodes, but varying with the allowable cell rate of the source. The allocation fairness problem is solved by normalizing the Nrm value to ensure that the inter-RM cell times for all sessions are fixed at a predetermined time interval. The selection of the predetermined time interval value is a trade-off between network overhead and the responsiveness of the traffic source to network congestion. The predetermined time interval is a function of link speed, buffer size and “burstiness” level of real time traffic sources.

摘要翻译： 用于分组ATM通信系统的数据传输流控制系统包括通过传输链路互连的多个节点。 通过将Nrm参数定义为允许的单元速率和采样周期的乘积，可以提高数据包或单元的可用带宽分配。 Nrm与在传输会话中的资源管理单元之间传输的数据单元的数量相关，并且被设置为与源节点和目的地节点之间的往返时间无关的数量，但是随着源的容许信元速率而变化。 通过归一化Nrm值来解决分配公平性问题，以确保所有会话的RM小区时间以预定的时间间隔被固定。 预定时间间隔值的选择是网络开销与流量源对网络拥塞的响应性之间的权衡。 预定时间间隔是链路速度，缓冲器大小和实时流量源的“突发性”级别的函数。

公开(公告)号：US5936940A

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

申请号：US701624

申请日：1996-08-22

申请人： Gerald Arnold Marin ,  Lap T. Huynh ,  Ken Van Vu ,  Raif O. Onvural ,  Levent Gun ,  Bouchung Lin

发明人： Gerald Arnold Marin ,  Lap T. Huynh ,  Ken Van Vu ,  Raif O. Onvural ,  Levent Gun ,  Bouchung Lin

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

CPC分类号： H04L12/5602 ,  H04L2012/5619 ,  H04L2012/5636

摘要： An enhanced adaptive rate-based congestion control system for packet transmission networks uses the absolute rather than the relative network queuing delay measure of congestion in the network. Other features of the congestion control system include test transmissions only after a predetermined minimum time, after the receipt of an acknowledgment from the previous test, or transmission of a minimum data burst, whichever takes longest. The congestion control system also provides a small reduction in rate at low rates and a large reduction in rates at high rates. A logarithmic rate control function provides this capability. Rate damping is provided by changing all of the values in a rate look-up tables in response to excessive rate variations. Finally, the fair share of the available bandwidth is used as the starting point for rates at start-up or when a predefined rate damping region is exited.

摘要翻译： 用于分组传输网络的增强的基于自适应速率的拥塞控制系统使用网络中的拥塞的绝对而不是相对网络排队延迟测量。 拥塞控制系统的其他特征仅在预定的最小时间之后，在从先前的测试接收到确认之后，或传输最小数据脉冲串（以较长者为准）为止包括测试传输。 拥挤控制系统还以低速率提供了较小的速率降低，并且高速率的速率大幅度降低。 对数速率控制功能提供此功能。 速率阻尼通过响应于过大的速率变化改变速率查找表中的所有值来提供。 最后，将可用带宽的公平份额用作启动速率或退出预定义速率阻尼区域的起始点。

公开(公告)号：US08078852B2

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

申请号：US12473764

申请日：2009-05-28

申请人： Muawya Mohamed Al-Otoom ,  Timothy Hume Heil ,  Anil Krishna ,  Ken Van Vu

发明人： Muawya Mohamed Al-Otoom ,  Timothy Hume Heil ,  Anil Krishna ,  Ken Van Vu

IPC分类号： G06F7/38 ,  G06F9/00 ,  G06F9/44 ,  G06F15/00

CPC分类号： G06F9/3848

摘要： An adaptive prediction threshold scheme for dynamically adjusting prediction thresholds of entries in a Pattern History Table (PHT) by observing global tendencies of the branch or branches that index into the PHT entries. A count value of a prediction state counter representing a prediction state of a prediction state machine for a PHT entry is obtained. Count values in a set of counters allocated to the entry in the PHT are changed based on the count value of the entry's prediction state counter. The prediction threshold of the prediction state machine for the entry may then be adjusted based on the changed count values in the set of counters, wherein the prediction threshold is adjusted by changing a count value in a prediction threshold counter in the entry, and wherein adjusting the prediction threshold redefines predictions provided by the prediction state machine.

摘要翻译： 一种自适应预测阈值方案，用于通过观察索引到PHT条目中的分支或分支的全局倾向来动态地调整模式历史表（PHT）中条目的预测阈值。 获得表示PHT条目的预测状态机的预测状态的预测状态计数器的计数值。 分配给PHT中的条目的一组计数器中的计数值根据条目的预测状态计数器的计数值而改变。 然后可以基于该组计数器中的改变的计数值来调整用于该条目的预测状态机的预测阈值，其中通过改变条目中的预测阈值计数器中的计数值来调整预测阈值，并且其中调整 预测阈值重新定义了由预测状态机提供的预测。

公开(公告)号：US06336167B1

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

申请号：US09415416

申请日：1999-10-08

申请人： Clark Debs Jeffries ,  Ken Van Vu ,  Mazin Sami Yousif

发明人： Clark Debs Jeffries ,  Ken Van Vu ,  Mazin Sami Yousif

IPC分类号： G06F1200

CPC分类号： G06F12/123

摘要： Cache management in a computer system is achieved by using a cache with dual stacks with storage locations for labels associated with data units stored either in the stack or in a separate cache memory unit. The first or preliminary stack is always refreshed following each label request using a conventional Least Recently Used (LRU) algorithm. If the requested label exists in either stack, the conventional LRU algorithm is also used to update the second stack. If the requested label does not exist in either stack and the bottom position in the second stack is empty, the label is written into the top position of the second stack and existing stack entries are pushed down one position. If the bottom position in the second stack is not empty, stack entries at and below a predetermined insertion point (which may be set statically or dynamically) are pushed down, the entry in the bottom position in the stack is discarded and the label is written into the predetermined insertion point in the second stack.

摘要翻译： 计算机系统中的缓存管理通过使用具有双堆栈的高速缓存来实现，该缓存具有与存储在堆栈中的数据单元相关联的标签的存储单元或单独的高速缓冲存储器单元中。 使用常规的最近最少使用（LRU）算法，在每个标签请求之后总是刷新第一或初步堆叠。 如果请求的标签存在于任一堆栈中，传统的LRU算法也用于更新第二堆栈。 如果请求的标签不存在于任一堆栈中，并且第二堆栈中的底部位置为空，则将标签写入第二堆栈的顶部位置，并将现有堆栈条目按下一个位置。 如果第二堆栈中的底部位置不为空，则在预定插入点（可以静态或动态设置）下方的堆栈条目被按下，堆叠中底部位置的条目被丢弃并且标签被写入 进入第二堆叠中的预定插入点。