Fair queue servicing using dynamic weights (dwfq)

0001This invention relates to the field of telecommunications, and more particularly to a method of fair queue servicing in asynchronous data networks, such as Asynchronous Transfer Mode (ATM) networks or more generally any packet switched network that supports more than one class of service.

0002The use of ATM by a continually increasing number of applications is driving a requirement to increase the number of service classes and to allow more flexibility in the service offerings. To support the application requirements, the ATM Forum is adding new service categories in new releases of ATM specifications. Furthermore, network providers are looking for the flexibility of defining multiple service classes for a given service category. The service classes are differentiated by their Quality-Of-Service requirements (QoS). The QoS requirements are configurable in accordance with a bidimensional matrix describing loss and delay. The delay jitter is another factor which needs to be bounded for some service classes.

0003Previously, three service categories were supported on an ATM network element, namely constant bit rate (CBR), variable bit rate (VBR) and unspecified bit rate (UBR). The CBR service is the only service that guarantees a bound on delay. It is used for time sensitive data such as voice and video.

0004These various services can be supported by traditional exhaustive round-robin queuing among two priority queues. However, this simple technique cannot be used when the number of queues increases beyond two, because of the high potential of starvation for lower priority queues. Furthermore, the exhaustive round robin can only guarantee bounds on delay and delay variation for the highest priority queue. The support of multiple service class in an ATM switching product or multiplexer requires a minimum of one queue per class.

0005A queue scheduling algorithm. Weighted Fair Queuing (WFQ), has been recently proposed in the literature (see S. Golestani, A self-clocked Fair Queuing scheme for broadband applications. INFOCOM 1994. June 1994).

0006This scheduling scheme allows any number queues (service classes) to be serviced, while providing fair and work conserving access to bandwidth. One of the key features of WFQ is that the CDV (Cell Delay Variation) is bounded for any service class, as long as it is given a minimum weight.

0007This proposed scheme can be implemented in ATM products. However, it has not been determined how to set the servicing weights efficiently to take into account the dynamically changing bandwidth requirement of each service class (connection addition/removal, ABR flow control, Early packet Discard).

0008An object of the invention is to provide a framework that ensures that the weights are set appropriately to guarantee the desired Quality of Service and modified in real-time to ensure that the dynamic allocation of bandwidth across the classes is optimized.

0009According to the present invention there is provided a method of fair queue servicing at a queuing point in a multi-service class packet switched network, wherein incoming packets are received in buffers and outgoing packets are scheduled by a weighted fair queue scheduler characterized in that real-time information of buffer usage along with the minimum bandwidth requirement is used to dynamically modify the weights of the weighted fair queue scheduler so as to cause buffer queue size to move toward a predetermined target value.

0010Preferably the minimum bandwidth requirement is extracted during connection admission control.

0011The method is particularly suitable for use in ATM networks.

0012The DWFQ (Dynamic Weighted Fair Queuing) can be implemented at any queuing point which arbitrates servicing between <b><i>n</i></b> queues (n≥2).

0013The invention also provides a fair queue servicing arrangement in a multi-service class packet switched network, comprising a weighted fair queuing controller, and buffer means for receiving incoming packets in queues, characterized in that further comprises means for monitoring buffer usage for each queue, means for determining the bandwidth requirements of each class of service, and a service weights manager for dynamically modifying the weights of said weighted fair queuing controller means in response to said buffer usage and bandwidth requirements.

0014Preferably, the means for monitoring buffer usage a queue growth monitor which performs real-time estimation of the queue growth in said buffer means.

0015The invention will now be described in more detail, by way of example only. with reference to the accompanying drawings, in which:- <ul id="ul0001" list-style="none"><li>Figure 1 is a diagram depicting the high level queuing scheme at an ATM switch;</li><li>Figure 2 shows the information provided by the Queue Growth Monitor;</li><li>Figure 3 illustrates the data flow between the key components of the system and the action of the Service Weight Manager (SWM); and</li><li>Figure 4 describes the process performed by the SWM.</li></ul>

0016Referring now to Figure 1, ATM cells 2 arrive at buffer 1 and are placed in queues 1¹, 1², ... 1ⁿ. From there the cells are passed to a weighted fair queuing unit 3. The buffer 1 is also connected to a queue growth monitor 4, which in turn is connected to congestion control unit 5, congestion analyzer 6, and connection admission controller 8, which in turn is connected to SVC &amp; PVC (Switched Virtual Circuit and Permanent Virtual Circuit) connection handling unit 7, and service class manager 10. Queue growth monitor 4, connection admission controller 8 and service class manager 9 are connected to service weights manager 9, which is connected to weighted fair queuing scheduler 3.

0017The key element of the Dynamic Weighted Fair Queuing (<b>DWFQ</b>) scheme is the service weight manager (SWM) 9, which dynamically modifies the service weights to be used by the WFQ Scheduler 3. It uses real-time information from the service class manager 10, the connection admission controller 8, and the Queue growth monitor 4.

0018The service class manager 10 configures the service classes. A service class is configured with a given value of delay (CTD - Cell Transfer Delay) and loss (CLR - Cell Ratio Loss) requirements. These parameters represent the maximum nodal delay and loss allowed in order to meet the end-to-end QoS requirements of the connection. The service classes are mapped into a priority table as exemplified in Table 1. The priority table is used later by the service weight manager to allocate remaining bandwidth. The priority table is updated when a service class definition is modified. The service class manager also dictates which traffic descriptors are used to compute the minimum bandwidth required by a connection of a given class. <tables id="tabl0001" num="0001"><table frame="all"><title>Table 1</title><tgroup cols="4" colsep="1" rowsep="1"><colspec colnum="1" colname="col1" colwidth="39.37mm" /><colspec colnum="2" colname="col2" colwidth="39.37mm" /><colspec colnum="3" colname="col3" colwidth="39.37mm" /><colspec colnum="4" colname="col4" colwidth="39.37mm" /><thead valign="top"><row><entry namest="col1" nameend="col4" align="center">• Example of a Queue Service Priority Mapping.</entry></row><row><entry namest="col1" nameend="col1" rowsep="0" align="left">CLR</entry><entry namest="col2" nameend="col4" align="left">CTD</entry></row><row><entry namest="col1" nameend="col1" /><entry namest="col2" nameend="col2" align="left">100 µs</entry><entry namest="col3" nameend="col3" align="left">500 µs</entry><entry namest="col4" nameend="col4" align="left">None</entry></row></thead><tbody valign="top"><row><entry namest="col1" nameend="col1" align="left">10^-9</entry><entry namest="col2" nameend="col2" align="left">1</entry><entry namest="col3" nameend="col3" align="left">3</entry><entry namest="col4" nameend="col4" align="left">6</entry></row><row><entry namest="col1" nameend="col1" align="left">10^-7</entry><entry namest="col2" nameend="col2" align="left">2</entry><entry namest="col3" nameend="col3" align="left">5</entry><entry namest="col4" nameend="col4" align="left">8</entry></row><row rowsep="1"><entry namest="col1" nameend="col1" align="left">10^-5</entry><entry namest="col2" nameend="col2" align="left">4</entry><entry namest="col3" nameend="col3" align="left">7</entry><entry namest="col4" nameend="col4" align="left">9</entry></row></tbody></tgroup></table></tables>

0019The connection admission controller (CAC) 8 computes the minimum bandwidth required for each service class. The minimum bandwidth is updated each time a connection of a given class is established or disconnected, based on its traffic descriptor.

0020Table 2 shows a typical example of which traffic descriptors that can be used to compute the minimum bandwidth for each basic service category relative to the queue service rate (SR). The CAC 8 communicates the minimum Weight table to the SWM every time the value of the minimum weights have changed by a factor of ξ. <tables id="tabl0002" num="0002"><table frame="all"><title>Table 2 ·</title><tgroup cols="3" colsep="1" rowsep="1"><colspec colnum="1" colname="col1" colwidth="52.50mm" colsep="1" /><colspec colnum="2" colname="col2" colwidth="52.50mm" /><colspec colnum="3" colname="col3" colwidth="52.50mm" /><thead valign="top"><row><entry namest="col1" nameend="col3" align="center">• Example of minimum weight table.</entry></row><row><entry namest="col1" nameend="col1" align="left">Queue_i</entry><entry namest="col2" nameend="col2" align="left">Category</entry><entry namest="col3" nameend="col3" align="left">min_Wi</entry></row></thead><tbody valign="top"><row><entry namest="col1" nameend="col1" align="left">Q₁</entry><entry namest="col2" nameend="col2" align="left">CBR</entry><entry namest="col3" nameend="col3" align="left">(Σ PCR)/SR</entry></row><row><entry namest="col1" nameend="col1" align="left">Q₂</entry><entry namest="col2" nameend="col2" align="left">RT-VBR</entry><entry namest="col3" nameend="col3" align="left">(Σ SCR)/SR</entry></row><row><entry namest="col1" nameend="col1" align="left">Q₃</entry><entry namest="col2" nameend="col2" align="left">NRT-VBR</entry><entry namest="col3" nameend="col3" align="left">(Σ SCR)/SR</entry></row><row rowsep="1"><entry namest="col1" nameend="col1" align="left">Q₄</entry><entry namest="col2" nameend="col2" align="left">UBR</entry><entry namest="col3" nameend="col3" align="left">0</entry></row></tbody></tgroup></table></tables>

0021The CTD is further taken into account in the target queue size (TQS) table, which is the maximum queue size allowed to limit the CTD. An example of TQS_i computation is shown in Table 3, for typical service categories. A zero TQS indicates that the queue can grow without limitation This table is computed by the CAC. <tables id="tabl0003" num="0003"><table frame="all"><title>Table 2</title><tgroup cols="3" colsep="1" rowsep="1"><colspec colnum="1" colname="col1" colwidth="52.50mm" /><colspec colnum="2" colname="col2" colwidth="52.50mm" /><colspec colnum="3" colname="col3" colwidth="52.50mm" /><thead valign="top"><row><entry namest="col1" nameend="col3" align="center">• Example of a target queue size computation.</entry></row><row><entry namest="col1" nameend="col1" align="left">Queue_i</entry><entry namest="col2" nameend="col2" align="left">Category</entry><entry namest="col3" nameend="col3" align="left">TQSi</entry></row></thead><tbody valign="top"><row><entry namest="col1" nameend="col1" align="left">Q₁</entry><entry namest="col2" nameend="col2" align="left">CBR</entry><entry namest="col3" nameend="col3" align="left">CTD/min_Wi</entry></row><row><entry namest="col1" nameend="col1" align="left">Q₂</entry><entry namest="col2" nameend="col2" align="left">RT-VBR</entry><entry namest="col3" nameend="col3" align="left">CTD/min_Wi</entry></row><row><entry namest="col1" nameend="col1" align="left">Q₃</entry><entry namest="col2" nameend="col2" align="left">NRT-VBR</entry><entry namest="col3" nameend="col3" align="left">0</entry></row><row rowsep="1"><entry namest="col1" nameend="col1" align="left">Q₄</entry><entry namest="col2" nameend="col2" align="left">UBR</entry><entry namest="col3" nameend="col3" align="left">0</entry></row></tbody></tgroup></table></tables>

0022The Queue Growth Monitor (QGM) 4 performs real-time estimation of the queue growth every <b>T</b>_<b>s</b> cell slots (sampling interval). The information provided by the Queue Growth monitor 4 to the SWM 9 consists of <b>ΔQi,</b> the Queue Growth Rate of output queue i during an interval of duration <b>Ts, Qi,</b> the length of output queue i at the sampling time, and Ai, the arrival rate during the same interval of time.

0023The corresponding parameters: queue size Qi, queue growth ΔQi, number of arrivals Ai are collected or each queue by the QGM 4 for each Ts interval. From these parameters, auxiliary parameters such as average arrival rate λi and service rate µi can be derived by the SWM 9: <ul id="ul0002" list-style="none"><li>λ_i : average arrival rate, λ_i = A_i ö T_s</li><li>µ_i : average service rate, µ_i = S_i ö T_s, where S_i = A_i - ΔQ_i is the number of cells served during T_s.</li></ul>

0024Figure 2 shows the information provided by the Queue Growth Monitor 4. Using this information for the CAC 8, the service class manager 9 and the queue growth monitor 4, the SWM computes the service eight for each queue _<i>i</i> (W_i) to be used during the next sampling interval.

0025As can be seen in Figure 3, which shows the data flow between the key components of the system and the action of the SWM 9, the queue weights. Wi, are updated using information provided by the Queue Growth monitor 4.

0026If <img file="EP0872088B1_D0001.tif" /> denotes the arrival rate of cells in queue <i>i</i> in the coming T_s interval, then ideally, the target service rate <img file="EP0872088B1_D0002.tif" /> can be calculated as:<maths id="math0001"><img file="EP0872088B1_D0003.tif" /></maths> This means at the end of next Ts interval, the queue size Qi will reach the target queue size TQSi. On the assumption that <img file="EP0872088B1_D0004.tif" /> remains unchanged from λ_i, the service weight W_i = <img file="EP0872088B1_D0005.tif" /> • T_s can be approximated as<maths id="math0002"><img file="EP0872088B1_D0006.tif" /></maths>

0027However, the assumption on the stable arrival rate may not hold, and also the actual number of serviced cells Si could be less than Wi; therefore a more conservative approach is ΔQ_i > 0, then Q_i+ΔQ_i, the predicted queue size at the end of the next Ts interval, is used to calculate the target service rate and weight. That is:<maths id="math0003"><img file="EP0872088B1_D0007.tif" /></maths> and<maths id="math0004"><math display="block"><mrow><msub><mrow><mtext>W</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><msub><mrow><mtext> ≅ λ</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msub><mrow><mtext> • T</mtext></mrow><mrow><mtext>s</mtext></mrow></msub><msub><mrow><mtext> + Q</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><msub><mrow><mtext> + ΔQ</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><msub><mrow><mtext> - TQS</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><msub><mrow><mtext> = A</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><msub><mrow><mtext> + Q</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><msub><mrow><mtext> + ΔQ</mtext></mrow><mrow><mtext>i</mtext></mrow></msub><msub><mrow><mtext> - TQS</mtext></mrow><mrow><mtext>i</mtext></mrow></msub></mrow></math><img file="EP0872088B1_D0008.tif" /></maths>

0028The detailed algorithm performed by the service weights manager 9 is shown in Figure 4. The queue size Q_i at the end of each interval T_s, the number of arrivals A_i during the previous interval T_s, and the change in queue size ΔQ_i are input at step 20. Step 21 determines whether the queue growth is positive: if yes, the service weight W_i is conservatively adjusted to bring the queue size to TQSi at step 22; if no, the service weight W_i is adjusted to bring the queue size to TQSi at step 23. The difference ΔW is determined in step 24.

0029Step 25 determines whether the shared weights pool is empty: if yes, Wi is set to min_Wi in step 26; if no, step 27 determines whether Ws ≥ ΔW_i: if yes, step 28 sets W_i = min_W_i + ΔW_i and W_s = W_s + ΔW_i; if no, step 29 sets W_i= min_W_i + W_s and W_s = 0.

0030Step 30 runs through all the W_i in the ordered list L and step 31 updates the weight table used by the Weighted Fair Queuing scheduler 3.

0031The described technique complies with ITU and ATM Forum standards and can be applied to any switching equipment which supports more than a single service class of service.