WO2007147544A1 - Method operable in a router for sizing a buffer - Google Patents
Method operable in a router for sizing a buffer Download PDFInfo
- Publication number
- WO2007147544A1 WO2007147544A1 PCT/EP2007/005343 EP2007005343W WO2007147544A1 WO 2007147544 A1 WO2007147544 A1 WO 2007147544A1 EP 2007005343 W EP2007005343 W EP 2007005343W WO 2007147544 A1 WO2007147544 A1 WO 2007147544A1
- Authority
- WO
- WIPO (PCT)
- Prior art keywords
- buffer size
- performance
- target
- router
- logical buffer
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Ceased
Links
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L45/00—Routing or path finding of packets in data switching networks
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L45/00—Routing or path finding of packets in data switching networks
- H04L45/60—Router architectures
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L47/00—Traffic control in data switching networks
- H04L47/10—Flow control; Congestion control
- H04L47/29—Flow control; Congestion control using a combination of thresholds
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L47/00—Traffic control in data switching networks
- H04L47/10—Flow control; Congestion control
- H04L47/30—Flow control; Congestion control in combination with information about buffer occupancy at either end or at transit nodes
Definitions
- the present invention relates to a method operable in a router for sizing a buffer.
- Router 10 joining a first network 12 to a second network 12' .
- Router 10 is employed to route packets (not shown) from the first network 12 to the second network 10' , ensuring the packets are delivered to an intended destination.
- Packets (not shown) are received by the router 10 from network 12 via an ingress link 16 and are transmitted from the router 10 to network 12' via an egress link 18.
- the router 10 comprises a buffer 14 to temporarily store incoming packets when the rate of arrival of packets received on the ingress link 16 can exceed the capacity of the egress link 18.
- link traffic may comprise a complex mix of bursty on/off flows, a mix of connection sizes, a mix of Transport Control Protocol (TCP) and User Datagram Protocol (UDP) traffic, a mix of congestion control action and other proprietary streaming algorithms.
- TCP Transport Control Protocol
- UDP User Datagram Protocol
- RED Random Early Detection
- ACQ active queue management
- RED employs a probabilistic mechanism based on average queue occupancy to choose which arriving packets to mark or drop before the queue overflows in an effort to indicate that congestion is imminent, instead of waiting until the congestion has become excessive. In this way, RED attempts to reduce buffer overflows and improve network fairness.
- AVQ Adaptive Virtual Queue, computes virtual capacity used by the router to drop or mark a real packet depending on congestion notification (arrival rate) .
- a virtual queue having a capacity less than or equal to the link capacity is maintained by the router.
- the virtual capacity is calculated and the buffer size of the virtual queue is updated accordingly. If the combination of the arrived packet and the buffer size of the virtual queue exceeds a physical buffer size, the packet is marked. Otherwise, the buffer size of the virtual queue is updated. In this way, the AVQ attempts to regulate link utilisation by anticipating overflow errors.
- the present invention provides a method operable in a router for sizing a buffer as defined in claim 1.
- Figure 1 illustrates a typical router connecting a first and second network
- Figure 2 illustrates architecture of a router comprising an active drop-tail buffer according to the preferred embodiment of the present invention.
- Figure 3 illustrates a flow diagram depicting a method of adjusting the size of the drop-tail buffer of Figure 2 according to the preferred embodiment of the present invention.
- FIG. 2 illustrates a router 20 operating in accordance with the preferred embodiment of the present invention.
- the router 20 comprises a buffer 24 of physical size q max and logical size q, such that the logical buffer size q is constrained to lie in the interval [0, q ma ⁇ ] •
- a first network (not shown) is connected to the router 20 via an ingress link 26, and a second network is connected to the router 20 via an egress link 28.
- the router 20 further comprises a controller 30, connected to the buffer 24 via feedback path 32.
- the logical buffer size q is varied by the controller 30 based on feedback 32 of the measured average link utilisation, u, of the egress link 28 with the aim of regulating utilisation. This approach allows the buffer 24 to adapt to changing traffic characteristics.
- the logical buffer size q is increased or decreased in accordance with deviation of the measured average link utilisation, u, from a target utilisation u 0 .
- Readjustment of the logical buffer size, q is governed by a proportional control law q ⁇ — K (uo-u) , where K is a design parameter, such that uo ⁇ u is reduced to a suitably small value.
- the measured average link utilization u may not be possible to achieve a measured average link utilisation u, equal to the target utilisation uo, in which case, it is desirable, that the measured average link utilization u, approach the target utilisation uo- This may be achieved by utilising the proportional control law. For example, if the target utilisation uo is below that which can be achieved even when the logical buffer size is zero, then uo ⁇ u is always negative and K(uo ⁇ u) will be clamped to zero if K>0, as required.
- readjustment of the logical buffer size q may be governed by an integral control law, for example, q ⁇ k + ⁇ ) ⁇ - q(k) + K (u o -u) .
- an integral control law for example, q ⁇ k + ⁇ ) ⁇ - q(k) + K (u o -u) .
- Advantageously employing such an integral control law prevents steady-state errors arising from variations in a level of utilisation achieved when the logical buffer size is small or zero.
- readjustment of the logical buffer size q may be governed by other forms of linear, nonlinear and switched control law provided that it maintains a stable feedback loop.
- the output of the control law utilised may be clamped in order to ensure that the logical buffer size is constrained to lie within the interval [0, q max ] .
- FIG. 3 A preferred embodiment of the present invention is illustrated in figure 3. Firstly, the drop-tail buffer 24 is assigned, an initial logical buffer size q, step 100.
- An average link utilisation, u, of the egress link 28 is measured, 110.
- the average link utilisation, u is compared, 120, with a target egress link utilisation value, uo.
- the buffer size q is decreased 130 as long as the router's 20, average loss rate, p, over some interval, is less than a loss rate threshold, PT.
- the buffer size q is unchanged, thereby ensuring network quality meets a certain standard.
- the buffer size q is increased 140 as long as the router's, 20, average loss rate, p, over some interval, is less than a loss rate threshold, PT.
- the buffer size q is unchanged.
- the logical buffer size q increases as the level of provisioning falls.
- a rising trend in logical buffer size therefore provides an early indication of growing link under provisioning that can be used, for example, to trigger link upgrade decisions.
- an indication of link under provisioning is provided.
- the method of the present invention requires coarse grained measurements only, for example, five minute average data.
- the method of the present invention may be implemented in a non-invasive manner through use of standard data logging interfaces and command connection.
- preferred embodiments of the invention provide a strategy to use network measurements to adjust buffer size with the objective of controlling router quality of service (QoS) parameters.
- buffer size is used to regulate utilisation with the objective of minimising queuing delay.
- buffer size is used to regulate loss rate with the objective of using the method to trigger link upgrades.
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
A method operable in a router for sizing a buffer, comprises assigning a buffer, provided in a router, a logical buffer size. A performance of a network connected to the router is measured and compared to a target performance. The logical buffer size is selectively adjusted in response to the comparison.
Description
Method operable in a Router for Sizing a Buffer
The present invention relates to a method operable in a router for sizing a buffer.
Referring now to figure 1, there is illustrated a typical router 10 joining a first network 12 to a second network 12' . Router 10 is employed to route packets (not shown) from the first network 12 to the second network 10' , ensuring the packets are delivered to an intended destination. Packets (not shown) are received by the router 10 from network 12 via an ingress link 16 and are transmitted from the router 10 to network 12' via an egress link 18.
The router 10 comprises a buffer 14 to temporarily store incoming packets when the rate of arrival of packets received on the ingress link 16 can exceed the capacity of the egress link 18.
However, problems arise when the rate of arrival of packets exceeds the buffer' s capacity to accommodate any more packets. When this occurs, packets are dropped as they attempt to enter the buffer queue, i.e. at the tail of the queue. Such buffers are known as Drop-Tail queues.
In order to maintain a high level of utilization of link capacity, and thereby an effective network, it is desirable for a buffer to be capable of accommodating bursty traffic, as well as avoiding excessively long periods when the queue is empty, which results in under provisioning of the link capacity.
In general, when devising buffer sizing strategies, a number of flows accessing the router and a mix of traffic in a network are considered. For example, in practice, link traffic may comprise a complex mix of bursty on/off flows, a mix of connection sizes, a mix of Transport Control Protocol (TCP) and User Datagram Protocol (UDP) traffic, a mix of congestion control action and other proprietary streaming algorithms.
It is known in the art to employ active queue management (ACQ) strategies for buffers. Random Early Detection (RED) is a form of ACQ. RED employs a probabilistic mechanism based on average queue occupancy to choose which arriving packets to mark or drop before the queue overflows in an effort to indicate that congestion is imminent, instead of waiting until the congestion has become excessive. In this way, RED attempts to reduce buffer overflows and improve network fairness.
Adaptive Virtual Queue, (AVQ) , computes virtual capacity used by the router to drop or mark a real packet depending on congestion notification (arrival rate) . A virtual queue having a capacity less than or equal to the link capacity is maintained by the router. On arrival of a packet, the virtual capacity is calculated and the buffer size of the virtual queue is updated accordingly. If the combination of the arrived packet and the buffer size of the virtual queue exceeds a physical buffer size, the packet is marked. Otherwise, the buffer size of the virtual queue is updated. In this way, the AVQ attempts to regulate link utilisation by anticipating overflow errors.
The present invention provides a method operable in a router for sizing a buffer as defined in claim 1.
Embodiments of the invention will now be described, by way of example, with reference to the accompanying drawings, in which:
Figure 1 illustrates a typical router connecting a first and second network;
Figure 2 illustrates architecture of a router comprising an active drop-tail buffer according to the preferred embodiment of the present invention; and
Figure 3 illustrates a flow diagram depicting a method of adjusting the size of the drop-tail buffer of Figure 2 according to the preferred embodiment of the present invention.
Figure 2 illustrates a router 20 operating in accordance with the preferred embodiment of the present invention. The router 20 comprises a buffer 24 of physical size qmax and logical size q, such that the logical buffer size q is constrained to lie in the interval [0, qmaχ] • A first network (not shown) is connected to the router 20 via an ingress link 26, and a second network is connected to the router 20 via an egress link 28. The router 20 further comprises a controller 30, connected to the buffer 24 via feedback path 32.
In the preferred embodiment of the present invention, the logical buffer size q is varied by the controller 30 based on feedback 32 of the measured average link utilisation, u, of the egress link 28 with the aim of regulating utilisation. This approach allows the buffer 24 to adapt to changing traffic characteristics.
In the preferred embodiment, the logical buffer size q is increased or decreased in accordance with deviation of the measured average link utilisation, u, from a target utilisation u0.
Readjustment of the logical buffer size, q, is governed by a proportional control law q <— K (uo-u) , where K is a design parameter, such that uo~u is reduced to a suitably small value.
In some cases, it may not be possible to achieve a measured average link utilisation u, equal to the target utilisation uo, in which case, it is desirable, that the measured average link utilization u, approach the target utilisation uo- This may be achieved by utilising the proportional control law. For example, if the target utilisation uo is below that which can be achieved even when the logical buffer size is zero, then uo~u is always negative and K(uo~u) will be clamped to zero if K>0, as required.
However, it will be appreciated that readjustment of the logical buffer size q may be governed by an integral control law, for example, q{k + \) <- q(k) + K (uo-u) . Advantageously employing such an integral control law
prevents steady-state errors arising from variations in a level of utilisation achieved when the logical buffer size is small or zero. However, when it is not possible to achieve a measured average link utilisation u equal to the target utilisation uo, ensuring that the measured average link utilization u, approach the target utilisation uo when a control law with integral action is used, it is advantageous to include an additional anti-windup feedback loop, whereby, q <- min(max(0,g), qmax) and q(k + ϊ) <— q(k) + K(uo~u) + Kaw(q(k)-q(k)) r with Kaw representing a gain of the anti- windup feedback.
It will be further appreciated that readjustment of the logical buffer size q may be governed by other forms of linear, nonlinear and switched control law provided that it maintains a stable feedback loop.
The output of the control law utilised may be clamped in order to ensure that the logical buffer size is constrained to lie within the interval [0, qmax] .
A preferred embodiment of the present invention is illustrated in figure 3. Firstly, the drop-tail buffer 24 is assigned, an initial logical buffer size q, step 100.
An average link utilisation, u, of the egress link 28 is measured, 110. The average link utilisation, u, is compared, 120, with a target egress link utilisation value, uo.
If the average link utilisation, u, exceeds a target link utilisation value, uo/ the egress link 28 is being over
utilised. In this case, the buffer size q is decreased 130 as long as the router's 20, average loss rate, p, over some interval, is less than a loss rate threshold, PT.
If the average loss rate, p, over some interval, is greater than or equal to the loss rate threshold, PT, the buffer size q is unchanged, thereby ensuring network quality meets a certain standard.
Alternatively, if the average link utilisation, u, is less than the target link utilisation value, uo, the egress link 28 is being under utilised. In this case, the buffer size q is increased 140 as long as the router's, 20, average loss rate, p, over some interval, is less than a loss rate threshold, PT.
If the average loss rate, p, over some interval, is greater than or equal to the loss rate threshold, PT, the buffer size q is unchanged.
In either case, the process returns to step 110 and repeats itself.
Thus, the logical buffer size q increases as the level of provisioning falls. A rising trend in logical buffer size therefore provides an early indication of growing link under provisioning that can be used, for example, to trigger link upgrade decisions. Thus, in one embodiment of the invention, when the logical buffer size approaches an upper threshold level, an indication of link under provisioning is provided.
Advantageously, the method of the present invention requires coarse grained measurements only, for example, five minute average data.
Furthermore, the method of the present invention may be implemented in a non-invasive manner through use of standard data logging interfaces and command connection.
As can be seen, preferred embodiments of the invention provide a strategy to use network measurements to adjust buffer size with the objective of controlling router quality of service (QoS) parameters. Preferably, buffer size is used to regulate utilisation with the objective of minimising queuing delay. Alternatively, buffer size is used to regulate loss rate with the objective of using the method to trigger link upgrades.
The present invention is not limited to the embodiments described herein, which may be amended or modified without departing from the scope of the present invention.
Claims
1. A method operable in a router for sizing a buffer, said method comprising: assigning a buffer, provided in a router, a logical buffer size; measuring a performance of a network connected to said router; comparing said measured performance to a target performance; and selectively adjusting said logical buffer size in response to said comparison.
2. The method of claim 1 wherein said selectively adjusting said logical buffer size comprises increasing said logical buffer size when said measured performance is substantially less than said target performance.
3. The method of any preceding claim wherein said selectively adjusting said logical buffer size comprises decreasing said logical buffer size when said measured performance is substantially greater than said target performance .
4. The method of any preceding claim wherein said selectively adjusting said logical buffer size in response to said comparison comprises not adjusting said logical buffer size when said measured performance is approximately equal to said target performance.
5. The method of any preceding claim wherein said comparing said measured performance to a target performance comprises comparing a measure of a link utilisation of said network to a target link utilisation performance.
6. The method of claim 5 wherein said comparing said link utilisation to a target link utilisation performance comprises comparing an egress link utilisation of said network to a target egress link utilisation.
7. The method of any preceding claim wherein said comparing said measured performance to a target performance comprises comparing a measure of packet loss rate to a target packet loss rate.
8. The method of claims 1-6 wherein said selectively adjusting said logical buffer size further comprises not adjusting said logical buffer size when a packet loss rate is approximately equal or greater than a target packet rate loss.
9. The method of any preceding claim further comprising providing an indication of link provisioning based on said adjusting of said logical buffer size.
10. The method of any preceding claim wherein said selectively adjusting of said logical buffer size is governed by one of: a proportional control law; an integral control law; a linear control law; a non-linear control law; or a switched control law.
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| IES2006/0464 | 2006-06-20 | ||
| IE20060464 | 2006-06-20 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| WO2007147544A1 true WO2007147544A1 (en) | 2007-12-27 |
Family
ID=38577663
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| PCT/EP2007/005343 Ceased WO2007147544A1 (en) | 2006-06-20 | 2007-06-18 | Method operable in a router for sizing a buffer |
Country Status (1)
| Country | Link |
|---|---|
| WO (1) | WO2007147544A1 (en) |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2010014208A1 (en) | 2008-07-28 | 2010-02-04 | Cellco Partnership D/B/A Verizon Wireless | Dynamic setting of optimal buffer sizes in ip networks |
| WO2017161240A1 (en) | 2016-03-17 | 2017-09-21 | T-Mobile Usa, Inc. | Dynamically optimized queue in data routing |
| CN119342007A (en) * | 2024-10-17 | 2025-01-21 | 北京中航通用科技有限公司 | RapidIO protocol signal buffer adjustment method and device |
Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6078919A (en) * | 1997-10-23 | 2000-06-20 | Lucent Technologies Inc. | Method and apparatus for delivery of data over a network based on determination of network parameters |
| US6366959B1 (en) * | 1997-10-01 | 2002-04-02 | 3Com Corporation | Method and apparatus for real time communication system buffer size and error correction coding selection |
| US6438604B1 (en) * | 1998-10-05 | 2002-08-20 | Canon Kabushiki Kaisha | Digital video network interface |
| EP1278353A2 (en) * | 2001-07-17 | 2003-01-22 | Avaya, Inc. | Dynamic jitter buffering for voice-over-ip and other packet-based communication systems |
-
2007
- 2007-06-18 WO PCT/EP2007/005343 patent/WO2007147544A1/en not_active Ceased
Patent Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6366959B1 (en) * | 1997-10-01 | 2002-04-02 | 3Com Corporation | Method and apparatus for real time communication system buffer size and error correction coding selection |
| US6078919A (en) * | 1997-10-23 | 2000-06-20 | Lucent Technologies Inc. | Method and apparatus for delivery of data over a network based on determination of network parameters |
| US6438604B1 (en) * | 1998-10-05 | 2002-08-20 | Canon Kabushiki Kaisha | Digital video network interface |
| EP1278353A2 (en) * | 2001-07-17 | 2003-01-22 | Avaya, Inc. | Dynamic jitter buffering for voice-over-ip and other packet-based communication systems |
Cited By (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO2010014208A1 (en) | 2008-07-28 | 2010-02-04 | Cellco Partnership D/B/A Verizon Wireless | Dynamic setting of optimal buffer sizes in ip networks |
| EP2310946A4 (en) * | 2008-07-28 | 2011-08-17 | Cellco Partnership Dba Verizon | DYNAMIC ADJUSTMENT OF OPTIMUM BUFFER SIZES IN IP NETWORKS |
| US8223641B2 (en) | 2008-07-28 | 2012-07-17 | Cellco Partnership | Dynamic setting of optimal buffer sizes in IP networks |
| US8897137B2 (en) | 2008-07-28 | 2014-11-25 | Cellco Partnership | Dynamic setting of optimal buffer sizes in IP networks |
| WO2017161240A1 (en) | 2016-03-17 | 2017-09-21 | T-Mobile Usa, Inc. | Dynamically optimized queue in data routing |
| EP3395023A4 (en) * | 2016-03-17 | 2019-06-05 | T-Mobile USA, Inc. | DYNAMICALLY OPTIMIZED WAITING QUEUE IN DATA ROUTING |
| CN119342007A (en) * | 2024-10-17 | 2025-01-21 | 北京中航通用科技有限公司 | RapidIO protocol signal buffer adjustment method and device |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Pan et al. | PIE: A lightweight control scheme to address the bufferbloat problem | |
| US12452185B1 (en) | Predictive management of a network buffer | |
| US7286485B1 (en) | Queue based multi-level AQM with drop precedence differentiation | |
| US7636308B2 (en) | Controlling packet congestion | |
| US7085236B2 (en) | Active queue management for differentiated services | |
| CN110808884B (en) | Network congestion control method | |
| US7047312B1 (en) | TCP rate control with adaptive thresholds | |
| US9634916B2 (en) | Signalling congestion | |
| US7158480B1 (en) | Feedback output queuing system, apparatus, and method | |
| Abbas et al. | Fairness-driven queue management: A survey and taxonomy | |
| US9438516B2 (en) | Call admission control and preemption control over a secure tactical network | |
| US20070115848A1 (en) | Adaptive application sensitive rate control system for packetized networks | |
| Thiruchelvi et al. | A survey on active queue management mechanisms | |
| Stanojevic et al. | Adaptive tuning of drop-tail buffers for reducing queueing delays | |
| US20030198220A1 (en) | Method for reducing packet data delay variation in an internet protocol network | |
| CN101567851B (en) | Method and equipment for shaping transmission speed of data traffic flow | |
| AU8043701A (en) | Domain based congestion management | |
| US20080304503A1 (en) | Traffic manager and method for performing active queue management of discard-eligible traffic | |
| WO2007147544A1 (en) | Method operable in a router for sizing a buffer | |
| US12301473B2 (en) | Excess active queue management (AQM): a simple AQM to handle slow-start | |
| Bless et al. | Policy-oriented aqm steering | |
| Agarwal et al. | Link utilization based AQM and its performance | |
| Singh et al. | Comparing different active queue management techniques | |
| Chitra et al. | Adaptive CHOKe: An algorithm to increase the fairness in Internet Routers | |
| Aweya et al. | WINTRAC: A TCP window adjustment scheme for bandwidth management |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| 121 | Ep: the epo has been informed by wipo that ep was designated in this application |
Ref document number: 07726052 Country of ref document: EP Kind code of ref document: A1 |
|
| NENP | Non-entry into the national phase |
Ref country code: DE |
|
| 122 | Ep: pct application non-entry in european phase |
Ref document number: 07726052 Country of ref document: EP Kind code of ref document: A1 |