• 专利附录
  • 专利说明
  • 权利要求
  • 类似技术
  • 同族专利
  • 引用文献
  • 法律状态
  • 优先权
    • 专利摘要:
    The invention relates to a flow limiter of a data transmission according to the technique of the token bucket, comprising a token counter (10) configured to be incremented at a rate determining the average rate of transmission; a frequency divider (12 ') connected to control the incrementation of the token counter from a clock (CK), the divider having an integer division rate (N); and a modulator (14) configured to alternate the division ratio between two different integers (N, N + 1) so as to make the resulting average flow rate tend to a programmed rate between two flow rates respectively corresponding to the two integers.
    公开号:FR3044188A1
    申请号:FR1561348
    申请日:2015-11-25
    公开日:2017-05-26
    发明作者:Amstel Duco Van；Alexandre Blampey；De Dinechin Benoit Dupont
    申请人:Kalray SA；
    IPC主号:
    专利说明:

    FLOW LIMITER OF TYPE "BUCKET BUCKET"
    TECHNICAL FIELD The invention relates to networks-on-a-chip and more particularly to flow rate devices of the "token bucket" type that can be used for injecting data streams into the network-on-chip at the level of routers.
    Background
    A "token bucket" type flow regulator or limiter operates in the following manner. A token counter, representing the bucket, is incremented at regular intervals. The token count saturates at a threshold (full bucket). At the arrival of a data packet, the size of the packet is compared to the count of chips in the bucket. If the count is sufficient, the packet is issued and the corresponding tokens are subtracted from the bucket. Otherwise, the package is rejected or waiting for the token count to be reached.
    Such a rate limiter can conform a data stream to a profile called σ-ρ (sigma-rho). The parameter p corresponds to an average rate, often a normalized value between 0 and 1 expressing a fraction of the nominal bandwidth of the transmission link. This parameter p corresponds to the filling rate of the token bucket. The parameter σ, often designated by the term "burstiness", expresses the irregularity of the flow rate tolerated during transmission. This parameter σ corresponds to the capacity of the bucket.
    More specifically, the size of a packet is generally expressed flits (of English "FLow digIT"), a flit corresponding for example to a transmittable word in a cycle of a clock setting the transmission link. Then, a stream conforming to a profile σ-ρ is such that the number of flits transmitted in any interval At is less than or equal to ρ · Δΐ + σ. If the parameter p is a dimensionless value between 0 and 1, the value At is the number of flits continuously transmitting in the interval At, or simply the number of clock cycles contained in the interval Δΐ. The incrementation of the token counter is generally based on the transmission clock. Thus, when the counter is incremented continuously, that is to say at each clock cycle, p = 1 is obtained. By dividing the clock frequency, the incrementation frequency of the counter of chips is divided, producing smaller p-values, for example 1/2, 1/3, 1/4, 1/5, etc., for respective division factors of 2, 3.4, 5 ...
    The degree of adjustment thus obtained for the parameter p may be insufficient in some applications. summary
    There is generally provided a flow limiting circuit of a data transmission according to the technique of the token bucket, comprising a counter of chips configured to be incremented at a rate determining the average rate of transmission; a frequency divider connected to control the incrementation of the token counter from a clock, the divider having an integer division rate; and a modulator configured to alternate the division ratio between two different integers so as to make the resulting average flow rate tend towards a rate programmed between two flow rates respectively corresponding to the two integers.
    The modulator may include an overflow counter connected to be incremented at the clock frequency by a fixed increment based on the difference between the programmed rate and the rate determined by a basic division rate selected from the two integers, the counter overflow being connected to the divider to alternate the division rate with each overflow.
    The frequency divider can be configured to apply the smallest of the two integers as the split rate by default and to increase the split rate at each overflow of the overflow counter.
    The frequency divider may comprise an auxiliary counter connected to be incremented at the clock frequency and to count to the smallest of the two integers, the overflow counter being connected to jump an increment to the auxiliary counter at each overflow.
    The programmed flow rate can be represented by a standardized flow rate between 0 and 1. The basic division rate can then be chosen equal to the integer part of the ratio between the chip counter increment and the normalized flow, and the increment. The overflow counter may be based on the fractional part of the ratio between the chip counter increment and the normalized rate. The increment of the overflow counter is expressed by the relation: 2k {c / p} -p / c rounded to the lower or higher integer, where p is the normalized flow, c the token counter increment, k the number of bits of the overflow counter, and {} denotes the fractional part.
    There is also provided a method of rate limiting a data transmission according to the token bucket technique, comprising the steps of incrementing a counter of chips at consecutive intervals whose length is variable between two discrete values multiple of the period a clock; select the two discrete values according to a programmed transmission rate; and applying the two discrete values to the chip counter at respective frequencies selected so that the average rate of incrementation of the chip counter corresponds to the programmed transmission rate.
    The method may include the steps of applying a first of the two discrete values by default as the increment interval of the token counter; incrementing an overflow counter at the clock rate by an increment based on the difference between the programmed rate and the rate corresponding to the first discrete value; and occasionally applying to the token counter the second discrete value as an increment interval at each overflow of the overflow counter.
    Brief description of the drawings
    Embodiments will be set forth in the following description, given in a nonlimiting manner with reference to the appended figures among which: FIG. 1 is a block diagram of an exemplary embodiment of a bucket type flow restrictor; tokens "; FIG. 2 is a block diagram of a flow restrictor embodiment providing a fine adjustment; FIG. 3 is a block diagram of a detailed embodiment of a flow limiter based on the principle of FIG. 2; FIGS. 4A to 4D are graphs showing the evolution of counters of the limiter of FIG. 3, in the context of an example; FIG. 5 is a graph illustrating a long-term evolution of the number of data transmitted in the context of the example of FIG. 4; and FIG. 6 schematically represents a system for issuing several competing data streams on a shared network link, in which speed limiters can be implemented.
    Description of embodiments
    In FIG. 1, a "token bucket" flow restrictor generally includes a token counter 10 which is connected to be incremented at the rate of INC pulses arriving at a clock input. The content of the token counter is limited to a maximum value defined by a parameter b, often programmable in a register. The increment to be applied can be an integer c greater than or equal to 1, programmable in another register. Thus, at each INC pulse, the content of the counter 10 increases from the value c, until saturation at the value b.
    The pulses INC are supplied from a clock CK by a frequency divider 12. The division rate N can be programmed in a register. The divider 12 is generally in the form of a counter designed to be reset as soon as its content reaches N. Thus, the divider 12 produces an INC pulse every N pulses of the clock CK. Whenever a data packet is available on transmission, the size of the packet is compared to the content of the counter 10. If the number of flits of the packet is less than or equal to the contents of the counter, the packet is transmitted and the counter is decremented by the size of the packet. Otherwise, the packet can be put on hold and the counter is not changed.
    Such a flow limiter makes it possible to program standardized flows according to discrete values p = c / N, where c and N are integers such that c <N. If it is desired to have a fine adjustment step between the programmable flows, N is chosen rather big. However, when N is large, there is a correspondingly large delay between two increments of the token counter, which increases the latency of packet transmission. Relatively high latency may be acceptable when the programmed rate is low (eg c / N = 1/100), but may be unacceptable when the programmed rate is high (eg c / N = 99/100, where the increments of chip counters only occur once every 100 clock cycles).
    Thus, for high rates, it is desired that N be rather close to 1, which considerably reduces the fineness of the adjustment step of p.
    FIG. 2 is a block diagram of a rate limiter embodiment that can offer a fine adjustment step regardless of the programmed rate p, and even makes it possible to program a rate p which is not a ratio of integers. .
    The N-divider of the rate limiter of FIG. 1 is replaced by a fractional divider 12 ', for example designed to apply one or the other of two integer division rates, here consecutive integers N and N + 1. The integer N can be the integer part of c / p, denoted by [c / p], from which it follows that the rate determined by the single rate N is greater than or equal to the programmed rate p, itself less than the rate determined by the rate N + 1 alone.
    In general, instead of two consecutive integers N and N + 1, it is possible to use any two integers NI and N2 that are chosen so that the programmed rate is between the limit rates determined by these two integers.
    The divider 12 'is controlled by a modulator 14 designed to determine the division rate to be applied at each increment as a function of the fractional part of c / p, denoted {c / p}. Here, the modulation is such that the ratio between the frequency of application of the rate N + 1 and the number of increments tends towards {c / p}, producing a rate of incrementation of the counter of chips equal on average to the programmed rate.
    A "modulation" is used because it seeks to alternate as much as possible the two division rates to linearize the incrementation of the token counter and regulate the resulting real rate. Such a phase locked loop modulator or delta-sigma modulator could be borrowed, but these systems are complex because they are designed to follow variable analog signals.
    FIG. 3 is a block diagram of a flow restrictor of the type of FIG. 2, illustrating in detail an example of a simple modulator, sufficient for the needs of the flow limiter. The modulator 14 comprises a counter 16 connected to be incremented at each clock cycle CK by an integer a, programmable in a register. The incrementation is done in open loop, that is to say without control of the overflow of the counter.
    The counter 16 having a limited size, say of k bits, its content evolves modulo 2k. In other words, the counter 16 regularly overflows to restart the count, which is why this counter is referred to hereinafter as an "overflow counter". If 2k is divisible by a, the content of the counter 16 evolves according to ramps of period equal to 2k / a clock cycles, starting at 0 and ending at 2k-1. If 2k is not divisible by a, the content of the counter 16 evolves according to aperiodic ramps which start at a value between 0 and a-1, and which end at a value between 2k-a and 2k-1.
    The overflows of the counter 16 are taken as reference to produce the desired modulation. The counter 16 may be designed to produce an OF pulse at each overflow. Then, the fractional divider 12 'can be configured by default to apply the division ratio N, and respond to each pulse OF to apply the division rate N + 1 punctually.
    The value of the increment a thus determines the frequency of application of the rate N + 1. To obtain the modulation sought here, the increment a is expressed by the relation: 2k {c / p} * p / c = 2k (l- [c / p] * p / c) rounded to the upper or lower integer value .
    The fractional divider 12 'can be realized, as represented, by a simple divider by N 12, the clock input of which is preceded by an AND gate 18. One of the inputs of the AND gate receives the signal CK clock, and the other the complement OF overflow impulses. With this configuration, the AND gate is transparent to the clock CK as long as the counter 16 does not overflow, resulting in division by N by default. At each overflow, the AND gate 18 masks the current clock pulse CK of the input of the divider 12. The divider "jumps" the pulse. This divider being generally a counter, the counter is frozen during a cycle, causing the delay of one cycle to the production of the next incrementation pulse INC of the token counter. In other words, the INC pulse is punctually produced at N + 1 cycles instead of N cycles.
    Figures 4A to 4D are graphs illustrating more clearly this operation in the context of an example. In this example, for a packet size of 32 flits, we used: P = 0.15, b = σ = 58, c = 1, k = 8, 2k = 256.
    These parameters produce the following values, calculated according to the relations mentioned previously: N = 6, a = 25.
    FIG. 4A represents the evolution of the overflow counter 16. This counter operates in freewheel mode and its first overflows take place in the cycles 12, 22, 32 and 42.
    FIG. 4B represents the evolution of a counter forming the divider 12, here a divider by 6. If the divider 12 were freewheeling, it would produce periodic ramps of 6 clock and amplitude cycles 5, as shown in FIG. first ramp. At the moments when the counter 16 (FIG. 4A) overflows, identified by return lines, the counter 12 is frozen during a clock cycle. Thus, the counter 12 remains at 4 during the two cycles 11 and 12, remains at 1 during the two cycles 21 and 22, remains at 4 during the two cycles 31 and 32, and remains at 1 during the two cycles 41 and 42.
    As a result, a division ratio of 7 (6 + 1) is applied to the second, fourth, fifth, and seventh ramps of FIG. 4B. From these first cycles, it is found that in 7 increments of the token counter, 4 were made over an interval of 7 cycles, and 3 were made over an interval of 6 cycles, resulting in an average interval of 6.57 cycles. This value is already close to the programmed interval of 1 / 0.15 = 6.67, and will get closer to it over time.
    FIG. 4C is a solid line showing the evolution of the token counter 10, initialized to the value φ = 58, assuming that a first packet of 32 bits becomes available on transmission in cycle 2.
    FIG. 4D, to which reference will be made at the same time as in FIG. 4C, represents the accumulation of emitted flits. The sending of the packet begins at cycle 3, while the counter of chips is decremented by 32, these operations being identified by a dashed pulse of the size of the packet.
    The token counter is then incremented by one unit at each of the cycles 6, 13, 19, 26, 33, 39, defined by the divider (FIG. 4B).
    The last Ait of the first packet is sent in cycle 33. It is assumed that a new packet is available as of cycle 34, but the token counter contains 31, which is insufficient to transmit the packet. The transmission of the new packet only begins at cycle 40, after the chip counter has reached 32 in cycle 39.
    Figure 5 is a long-term extension, over nearly 2500 cycles, of the graph of Figure 4C, assuming that packets are permanently available on transmission. The dashed lines represent the limits that must be respected by the evolution of the accumulation of flits emitted to conform to a profile σ-ρ.
    The low limit line is defined by y = pt = 0.15t, where t is the time expressed in number of clock cycles.
    The upper limit line is defined by y = pt + σ = 0,15t + 58.
    These limit lines are defined according to the exact programmed value of p. It is noted that the cumulation of flits emitted perfectly respects these limits, although 1 / p is not an integer.
    The resolution with which the rate p can be programmed depends on the size k of the overflow counter, N, and c. More specifically, it is equal to 2'kc / N for N <2k. When N is greater than 2k, the increment a is always zero and the resolution is c / (N (N + 1)).
    FIG. 6 schematically represents an example of a system for sending several competing streams on a shared network link L, as evoked in the patent application US 2014-0301206. Several flow restrictors as described herein can be used in such a system.
    The system includes a CPU processor, a MEM memory, and a DMA direct memory access circuit, interconnected by a system bus B. An NI network interface is connected to send over the network link L data provided via the circuit DMA. This network interface comprises several queues 20, for example eight, each of which can be associated with a connection, a virtual channel, or more generally a different transmission session.
    An arbitrator ARB can be provided to manage the filling of the queues, for example according to a Weighted Fair-Queuing (WFQ). The dump of the queues on the network link L is managed by an REGL controller. This regulator may include a flow limiter per file, the parameters of which are programmed by the processor when the system is turned on. The flow limiters can be configured so that each is activated in turn in a circular manner. The active limiter then sends packets taken in its queue until its token counter is exhausted or the queue is empty.
    Many variations and modifications of the embodiments described herein will be apparent to those skilled in the art. For example, although a fractional divider has been described that operates by default with the smaller division rate (N) and is controlled punctually by the modulator to apply the higher division rate (N + 1), the Dual configuration can be used, namely that the divisor operates by default with the higher division rate (N + 1) and that this rate is punctually switched to the smaller rate (N) by the modulator. In this case, we can use the value 1 - {c / p} instead of {c / p} in the different relations described.
    权利要求:
    Claims (8)
    [1" id="c-fr-0001]
    claims
    A rate limiting circuit of a data transmission according to the token bucket technique comprising: a token counter (10) configured to increment at a rate determining the average rate of transmission; A frequency divider (12 ') connected to control the incrementation of the token counter from a clock (CK), the divider having an integer division rate (N); and a modulator (14) configured to alternate the division ratio between two different integers (N, N + 1) so as to make the resulting average flow rate tend to a programmed rate between two flow rates respectively corresponding to the two integers.
    [2" id="c-fr-0002]
    The circuit of claim 1, wherein the modulator comprises an overflow counter (16) connected to be incremented at the clock rate (CK) by a fixed increment (a) based on the difference between the programmed rate and the rate determined by a base division rate selected from the two integers (N, N + 1), the overflow counter being connected to the divider to alternate the division rate at each overflow.
    [3" id="c-fr-0003]
    3. Circuit according to claim 2, wherein the frequency divider (12 ') is configured to apply by default the smallest (N) of the two integers as the division rate and to increase the division rate at each point overflow of the counter. overflow.
    [4" id="c-fr-0004]
    The circuit of claim 3, wherein the frequency divider comprises an auxiliary counter (12) connected to be incremented at the clock frequency (CK) and to count to the smallest of the two integers (N), the overflow counter being connected to skip an increment to the auxiliary counter at each overflow.
    [5" id="c-fr-0005]
    5. Circuit according to claim 2, in which: the programmed flow rate is represented by a standardized flow rate (p) between 0 and 1; the base division rate (N) is chosen equal to the integer part of the ratio between the chip counter (c) and the normalized rate, and • the increment (a) of the overflow counter is based on the fractional part of the ratio between the chip counter increment and the normalized rate.
    [6" id="c-fr-0006]
    The circuit of claim 5, wherein the increment of the overflow counter is expressed by the relation: 2k {c / p} * p / c rounded to the lower or higher integer, where p is the normalized rate, c the chip counter increment, k the number of bits of the overflow counter, and {} denotes the fractional part.
    [7" id="c-fr-0007]
    7. A method of limiting the rate of a data transmission according to the technique of the token bucket, comprising the following steps: • incrementing a token counter (10) at consecutive intervals whose length is variable between two discrete values (N , N + 1) multiples of the period of a clock (CK); • select the two discrete values according to a programmed transmission rate; and • applying the two discrete values to the chip counter according to respective frequencies selected so that the average incrementation rate of the token counter corresponds to the programmed transmission rate.
    [8" id="c-fr-0008]
    The method of claim 7, comprising the steps of: • by default, applying a first one of the two discrete values (N) as the incrementation interval of the token counter; Incrementing an overflow counter (16) at the clock frequency (CK) by an increment (a) based on the difference between the programmed rate and the rate corresponding to the first discrete value; and • occasionally applying to the token counter the second discrete value (N + 1) as the increment interval at each overflow of the overflow counter.
    类似技术:
    公开号 | 公开日 | 专利标题
    EP3174255B1|2019-08-14|Token bucket flow-rate limiter
    EP2859696B1|2017-08-02|Preventing overestimation of available bandwidth in adaptive bitrate streaming clients
    WO2014116449A1|2014-07-31|System and method for robust adaptation in adaptive streaming
    FR2854018A1|2004-10-22|Data packet e.g. MPEG flow, traffic controlling method for use in network e.g. Internet protocol network, involves accepting or refusing data packets based on possibility to attribute token according to availability of tokens
    EP2940960A1|2015-11-04|Method and device for scheduling packets to be routed in a network with implicit determination of the packets to be given priority treatment
    EP2795854A1|2014-10-29|System for the transmission of concurrent data streams over a network
    WO2013184442A1|2013-12-12|Stabilization of adaptive streaming video clients through rate limiting
    FR2908585A1|2008-05-16|Coded data i.e. video, transmitting method for telecommunication system, involves determining subset of data of parameters of buffer memory relative to flow measurement of network card representing bandwidth useable for network
    EP1692824A1|2006-08-23|Method and server for controlling data flows in a telecommunications network
    FR2662887A1|1991-12-06|METHOD FOR REDUCING THE LOW-FREQUENCY COMPONENT OF THE TRIGGER IN A DIGITAL DATA TRANSMISSION SYSTEM
    FR2858730A1|2005-02-11|Scheduling information recovering method for e.g. Ethernet network, involves using frequency or phase modulated signal for transmitting additional information to recover clock signal, and recovering clock signal using information
    EP2497235B1|2013-08-14|Diagnostic tool for broadband networks
    EP2680603A1|2014-01-01|Processing technique to provide real-time content to client entities
    US20150016285A1|2015-01-15|Systems and methods to handle codec changes in call quality calculations
    FR2845783A1|2004-04-16|Clock generator for dividing primary frequency by nominated decimal number, comprises a modulation circuit, a modulation distribution circuit and two divisors with down counters
    GB2577610A|2020-04-01|Improved congestion response
    Ameur et al.2015|Evaluation of gateway-based shaping methods for HTTP adaptive streaming
    WO2019185372A1|2019-10-03|Congestion response for timely media delivery
    US20180167431A1|2018-06-14|Client-side ack regulation based adaptive streaming method and apparatus
    ES2703153T3|2019-03-07|Method, device, software product and storage medium for distributing file requests in adaptive streaming systems
    FR2594277A1|1987-08-14|Device for synchronising packets by dual phase-lock loop
    US10609111B2|2020-03-31|Client-driven, ABR flow rate shaping
    US20210297358A1|2021-09-23|Improved congestion response
    EP1293909B1|2010-11-10|Dynamic access control of a function to a shared resource
    EP3085035B1|2019-03-13|Technique for signalling congestion in a packet communication network
    同族专利:
    公开号 | 公开日
    CN106850456A|2017-06-13|
    CN106850456B|2022-01-11|
    US10250697B2|2019-04-02|
    US20170149908A1|2017-05-25|
    FR3044188B1|2017-12-22|
    EP3174255B1|2019-08-14|
    EP3174255A1|2017-05-31|
    引用文献:
    公开号 | 申请日 | 公开日 | 申请人 | 专利标题
    US20040062259A1|2002-09-27|2004-04-01|International Business Machines Corporation|Token-based active queue management|
    WO2009051533A1|2007-10-19|2009-04-23|Telefonaktiebolaget Lm Ericsson |Method and arrangement for scheduling data packets in a communication network system|
    US8315271B2|2004-03-26|2012-11-20|Qualcomm Incorporated|Method and apparatus for an ad-hoc wireless communications system|
    CN100568849C|2005-08-29|2009-12-09|中兴通讯股份有限公司|A kind of message rate-limiting method based on token bucket|
    JP4263712B2|2005-09-26|2009-05-13|日本電信電話株式会社|Traffic shaping apparatus and traffic shaping method|
    US7605665B2|2007-05-25|2009-10-20|Broadcom Corporation|Fractional-N phase locked loop|
    US8497716B2|2011-08-05|2013-07-30|Qualcomm Incorporated|Phase locked loop with phase correction in the feedback loop|
    FR2984656B1|2011-12-19|2014-02-28|Kalray|SYSTEM FOR TRANSMITTING CONCURRENT DATA FLOWS ON A NETWORK|
    CN102970238B|2012-11-22|2015-09-30|华为技术有限公司|A kind of method and apparatus of flow control|
    US9559968B2|2015-03-23|2017-01-31|Cisco Technology, Inc.|Technique for achieving low latency in data center network environments|US10917015B2|2017-08-31|2021-02-09|Active-SemiInc.|Multiphase converter system and control method|
    US11159455B1|2018-12-28|2021-10-26|Innovium, Inc.|Reducing power consumption in an electronic device|
    CN112805971A|2019-01-07|2021-05-14|华为技术有限公司|Traffic shaping method and related equipment|
    法律状态:
    2016-11-24| PLFP| Fee payment|Year of fee payment: 2 |
    2017-05-26| PLSC| Publication of the preliminary search report|Effective date: 20170526 |
    2017-11-16| PLFP| Fee payment|Year of fee payment: 3 |
    2019-11-22| PLFP| Fee payment|Year of fee payment: 5 |
    2021-08-06| ST| Notification of lapse|Effective date: 20210705 |
    优先权:
    申请号 | 申请日 | 专利标题
    FR1561348A|FR3044188B1|2015-11-25|2015-11-25|FLOW LIMITER OF TYPE "BUCKET BUCKET"|FR1561348A| FR3044188B1|2015-11-25|2015-11-25|FLOW LIMITER OF TYPE "BUCKET BUCKET"|
    EP16197547.9A| EP3174255B1|2015-11-25|2016-11-07|Token bucket flow-rate limiter|
    US15/356,151| US10250697B2|2015-11-25|2016-11-18|Token bucket flow-rate limiter|
    CN201611059570.3A| CN106850456B|2015-11-25|2016-11-25|Token bucket flow rate limiter|
    [返回顶部]