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 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.

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 u ₀ .

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 (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. 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), q _max ) and q(k + ϊ) <— q(k) + K(uo~u) + K _a w(q(k)-q(k)) r with K _aw 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, q _max ] .

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.