Optimal buffer management scheme with dynamic queue length thresholds for ATM switches

[0002] The present invention relates to a buffer management scheme for ATM switches. Specifically, the present invention provides an optimal buffer management scheme for ATM switches using dynamic queue lengths. The present invention is embodied in an ATM switch that uses a dynamic queue threshold and a method of dynamically setting a common threshold for queues in an ATM switch.

[0003] Conventionally, ATM switch architectures used buffering to accommodate cells whose service has been delayed due to contention for bandwidth or temporary congestion within the switch. Literature. See E. W. Zegura, “Architectures for ATM Switching Systems”, IEEE Communications Magazine, pp. 28-37, February, 1993. Among these architectures, the shared buffer memory switches are preferred because of they utilize buffers more efficiently. By sharing the buffer, e.g., among all output ports, and taking advantage of the statistical multiplexing on input traffic, shared buffer ATM switches are able to achieve the same cell delay and loss performance with a smaller buffer size per port. Such a buffer size reduction effect is even more significant when the traffic is bursty and traffic load is uneven.

[0004] In an ATM switch, the buffer memory is usually shared at several different levels. For example, the buffer can be logically partitioned and shared by different service classes, i.e., CBR, VBR, ABR, UBR, etc. As mentioned above, the buffer can be shared among queues corresponding to different output ports. If per-VC queuing is adopted, the buffer can be shared among queues corresponding to different VCs.

[0005] However, the shared-memory switches without buffer management procedures do not perform well under overload conditions. See M. I. Irland, “Buffer management in a packet switch,” IEEE Trans. Commun., vol. COM-26, pp. 328-337, March 1978. A key problem is fairness among the various output ports. The statistical sharing of the buffer memory introduces the possibility that a small group of output ports consume most of the memory. Such an excessive use memory by some ports prevent cells destined for less utilized ports from gaining their fair share of memory. In a worst case scenario even access is prevented.

[0006] One conventional solution to such problem is setting restrictions on the amount of buffering a port can use. That is, each queue has a threshold of the maximum amount of memory it can access as well as a minimum amount guaranteed for itself.

[0007] Different threshold-setting methods have been proposed and analyzed in literature. See F. Kamoun and L. Kleinrock, “Analysis of Shared Finite Storage in a Computer Network Node Environment Under General Traffic Conditions”, IEEE Trans. Commun., Vol.Com-28, No. 7, pp. 992-1003, July, 1980. There are generally two techniques of setting queue thresholds.

[0008] One technique is called static threshold (ST). In this method, buffer thresholds are pre-set for each queue, by the network management system (NMS). An arriving cell is accepted only if the corresponding queue length is less than the given threshold value. The ST method is simple to implement and only requires the corresponding queue counters and a comparator. In choosing the static thresholds for different queues, the NMS is required to know the characteristics and the statistics of the traffic. The traffic arriving at the queues are required to be in line with their descriptions. Therefore, the ST method is more appropriate for traffic at class level, i.e., CBR, VBR and UBR, in which the traffic is more predictable for the whole class although they may fluctuate substantially with respect to different port queues and individual connections within the class.

[0009] Another technique is called dynamic threshold (DT). In this method, buffer thresholds are dynamically adjusted according to the changing traffic load. The DT technique allows the overloading traffic to get access to memory as long as its queue has not exceeded its fair share of the memory, i.e., the dynamic threshold. Therefore, a good dynamic threshold method should improve the overall switch bandwidth utilization while ensuring fair sharing of buffer memory among different queues. In general, DT schemes require more processing power and are more appropriate for buffer management at port or VC level. In these levels traffic load variation may fluctuate substantially (although mostly lasting in a shorter time span) among different queues. The relative short time scale with respect to the traffic load variation at port and VC level requires any DT scheme to be simple for implementation practice.

[0010] For the above two schemes, performances in various traffic conditions have been compared through a comprehensive simulation study. See Choudhury and Hahne in A. K. Choudhury and E. L. Hahne, “Dynamic Queue Length Thresholds in a Shared-Memory Packet Switch”, IEEE/ACM Trans. Networking, Vol. 6, No., pp. 130-140, April, 1998. In particular, they have proposed a simple and elegant DT scheme that ensures the fair sharing of buffer memory with a certain amount of buffer being unallocated. However, in this scheme the buffer memory utilization is low when only a small number of queues are overloaded.

[0011] In order to overcome the problems in conventional methods it is an object of the present invention to provide an ATM switch that uses a dynamic queue threshold scheme that enables efficient utilization of available memory regardless of the numbers of overloaded queues.

[0012] Another objective of the present invention is to provide a hierarchical buffer management scheme using ST and DT algorithms. A further object is to provide a new dynamic queue threshold algorithm, which improves buffer utilization. In order to accomplish the objects of the present invention there is provided An ATM switch using a dynamic queue threshold scheme, said ATM switch comprising K output port queues and a buffer of B cells sharing said K output port queues, wherein a common threshold is dynamically set for the K output port queues, the common threshold being changed to a new value from an old value when a new cell arrives at any of said K output queues, said new value being a maximum of a length of said any of said K output queues plus one and said old value when total queue length is less than a preset value times B and, said new value being a maximum of a said old value minus one and a statically set minimum buffer threshold when total queue length is greater than or equal to a preset value times B, wherein said preset value is greater than 0.

[0013] Preferably the length of each of said K output queues fluctuates based on variations in an incoming traffic load and a service bandwidth allocated to said each of said K output queues.

[0014] Preferably, a new cell is accepted to a specific queue when a length of said specific queue is less than the new value and total queue length is less than B.

[0015] Preferably, the statically set minimum buffer threshold is equal to zero by default. Preferably, a small amount of buffer B is allocated for some predetermined operations.

[0016] Preferably, buffer memory is allocated to VCs within said each of said K output queues, further using the dynamic queue threshold scheme.

[0017] Preferably, the dynamic queue threshold scheme is applied to multiple levels of dynamic buffers.

[0018] Another aspect of the present invention is a method of dynamically setting a common threshold T(t) for K queues in an ATM switch comprising said K queues, a buffer of B cells shared by said K queues, each of said K queues having a queue length of Q_k(t) at time t and k=1,2 . . . K, with Q_k(t) fluctuating with incoming traffic load and service bandwidth allocated to output port k, said method comprising:

[0019] setting a dynamic threshold T(t) wherein

[0020] T_new(t)=max(Q_k(t)+1, T_old) when Q(t)<α*B;

[0021] T_new(t)=max(T_old−1, T_m) when Q(t)>=α*B;

[0022] wherein Q(t) is a total queue length at time t and 0<α<=1, and

[0023] T_mis a minimum buffer threshold statically set, updating T_new(t) and accepting a new arriving cell at output port k at time t if Q_k(t)<T_new(t) and Q(t)<B, otherwise blocking said new arriving cell. Yet another aspect of the present invention is a method of dynamically setting a common threshold T(t) for K queues in an ATM switch comprising said K queues, a buffer of B cells shared by said K queues, each of said K queues having a queue length of Q_k(t) at time t and k=1,2 . . . K, and l=1, 2, . . . L_kwith Q_k(t) fluctuating with incoming traffic load and service bandwidth allocated to output port k, each queue comprising L_kVCs and each VC queue of port K has a queue of length Q_kl(t) said method comprising:

[0024] setting a dynamic threshold TP(t) for each output queue wherein

[0025] TP_new(t)=max(Q_k(t)+1, TP_old) when Q(t)<α*B;

[0026] TP_new(t)=max(TP_old−1, T_m) when Q(t)>=α*B;

[0027] setting a dynamic threshold TV_k(t) for each VC assigned to queue k wherein

[0028] TV_k^new(t)=max(Q_kl(t)+1, TV_k^old) when Q(t)<β*TP(t);

[0029] TV_k^new(t)=max(TV_k^old−1, T_m) when Q(t)>=β*TP(t);

[0030] wherein Q_k(t) is a total queue length for kth queue at time t and 0<α<=1, 0<β<=1 and T_mis a minimum buffer threshold statically set, updating TP(t) and TV_k(t) and accepting a new arriving cell at output port k at time t if Q_k(t)<TP(t) and Q_kl(t)<TV_k(t) and Q(t)<B, otherwise blocking said new arriving cell.

[0031] The above objectives and advantages of the present invention will become more apparent by describing in detail preferred embodiments thereof with reference to the attached drawings in which:

[0032] FIG. 1 shows an ATM switch with input and output queuing modules.

[0033] FIG. 2 shows a hierarchical buffer memory allocation scheme at different levels: group, class, sub-class, port/line, VC.

[0034] FIG. 3 shows a dynamic buffer allocation at port level with each VC destined to a different port.

[0035] FIG. 4 shows a dynamic buffer allocation at port and VC levels.

[0036] Buffer Management in ATM Switches

[0037] In ATM switches, buffer memory is divided and shared in several different ways: among queues belonged to different traffic classes; among queues destined to different output ports; among queues of different VCs if per-VC queuing is adopted, etc. In FIG. 1 an architectural layout of an ATM switch with input and output queuing is shown. In this embodiment the switch has K input modules and K output modules with similar structure and functionalities. At each input module, the buffer memory is shared and logically divided in a hierarchical way as shown in FIG. 2.

[0038] The total buffer memory at an input module is B cells, and there are N traffic classes. The N traffic classes consist of CBR, VBR (real-time and non real-time), ABR and UBR, etc. Each traffic class belongs to one of M groups, M<N. Each group contains traffic classes of similar statistical characteristics, e.g., all non real-time VBR classes may belong to one group. The total buffer B is partitioned and dedicated to each group. Group m, m=1, 2, . . . , M, is allocated a dedicated BG_mmemory and $\sum _{m=1}^M{\mathrm{BG}}_m\le B$

[0039] There is no sharing of memory between groups and BG_mare static group buffer thresholds chosen and tuned by network management system. The traffic classes assigned to group m can share the group memory BG_min such a way that the maximum number of buffer class i (where class i is assigned to group m) can use is also limited by ${\mathrm{BC}}_i,i=1,2,\dots ,N,\mathrm{and}$ $\sum _{i\in m}{\mathrm{BC}}_i\ge {\mathrm{BG}}_m,\mathrm{and}{\mathrm{BC}}_i\le {\mathrm{BG}}_m$

[0040] This ensures that while maximizing the buffer utilization by complete sharing within a group, there is no excessive consuming of buffer memory by any one class in a group. For each traffic class i of buffer allocation BC_i, J sub-classes for cells with different loss or delay priorities may be present. The buffer threshold for sub-class j is set to be TC_ij, J=1, 2, . . . , J. The choice of TC_ijis made by applying certain queuing models. See F. Kamoun and L. Kleinrock, “Analysis of Shared Finite Storage in a Computer Network Node Environment Under General Traffic Conditions”, IEEE Trans. Commun., Vol.Com-28, No. 7, pp. 992-1003, July, 1980.

[0041] Similar to the group level allocation BG_m, the buffer thresholds at class and sub-class levels (BC_iand TC_ij) are statically chosen and tuned by network management system. Within each class, the buffer management is furthered categorized into two levels: there are queues for cells to K different output ports with TP_idenoting the common threshold for all K queues; for each output port, there are queues for different VCs, if per-VC queuing is adopted, with TV_ikdenoting the common threshold for all VCs destined to output port k, k=1, 2, . . . , K.

[0042] Unlike the buffer allocation at group and class levels, the queue thresholds at port and VC levels (TP_iand TV_ik) are dynamically updated to the changing traffic conditions. The reasons for using dynamic thresholds for port and VC level buffer management is that the variation of traffic load tend to be substantial at these levels, and a dynamic threshold can accommodate the transient behavior of traffic load much better than a static one. In a conventional static threshold scheme the port queue threshold is set as: ${\mathrm{TP}}_I=\frac{{\mathrm{BC}}_i}{\sqrt{K}}.$

[0043] See F. Kamoun and L. Kleinrock, “Analysis of Shared Finite Storage in a Computer Network Node Environment Under General Traffic Conditions”, IEEE Trans. Commun., Vol.Com-28, No. 7, pp. 992-1003, July, 1980.

[0044] In the next section, an embodiment of the novel dynamic threshold scheme according to the present invention is described. This method provides a fair and optimal sharing of buffer memory. It should be readily apparent to a skilled artisan that although this embodiment is presented in the context of port and/or VC level queue length thresholds, the scheme can be directly applied to any problem that requires dynamic fair sharing of buffer memory.

[0045] Dynamic Queue Threshold Scheme

[0046] The embodiment described herein is an ATM switch. In the described embodiment it is assumed that the ATM switch has K output ports and a buffer of B cells, shared by the corresponding K output queues. Q_k(t) is the queue length for output queue k at time t, k=1, 2, . . . , K. In a preferred embodiment Q_k(t) may fluctuate as the incoming traffic load for output port k and the service bandwidth allocated to output port k vary. If all the K output queues are treated equally, to ensure fair-sharing of buffer space B, each queue should be able to access at least B/K buffer memory (the fair share) when it is overloaded. On the other hand, to efficiently utilize the buffer, i.e., to achieve maximum buffer sharing, an individual overloaded queue may use any available buffer memory that are not used or demanded by other queues.

[0047] The dual goals stated above are achieved by dynamically setting a common threshold T(t) for all K queues. in this scheme, the following algorithm dynamically sets the T(t):

[0048] When a cell to output port k arrives at time t, $\begin{array}{cc}{T}_{\mathrm{new}}\left(t\right)=\{\begin{array}{cc}\max \left(Q_k\left(t\right)+1,T_{\mathrm{old}}\right),& \mathrm{if}Q\left(t\right)<\alpha *B,\\ \max \left(T_{\mathrm{old}}-1,T_m\right),& \mathrm{if}Q\left(t\right)\ge \alpha *B,\end{array}& \left(1\right)\end{array}$

[0049] where $Q\left(t\right)=\sum _{k=1}^K{Q}_k\left(t\right),$

[0050] representing total queue length at time t and 0<α≦1. The T_mrepresents the minimum buffer threshold statically set for each queue. By default, T_m=0. Therefore, the arriving cell to output port k is accepted at time t to the k-th queue if Qk(t)<T_new(t) and Q(t)<B; otherwise, the cell is blocked. In either case, the value of common threshold T_oldis then updated by the value of T_new(t).

[0051] Note that in Eq.(1), the parameter α controls the amount of memory to be shared. For a complete buffer sharing, α is set to be one and thus when queues are overloaded, 100% buffer utilization can be achieved while the memory is fairly shared among different queues. In a preferred embodiment, a small amount buffer may be set aside specifically for some operations (i.e., RM cell insertion and end-of-message cell insertion) by adjusting parameters α and T_min Eq.(1).

[0052] Multi-level Dynamic Queue Thresholds

[0053] In the previous section an embodiment was describes that used the dynamic queue threshold scheme of the present invention to manage buffer memory for different queues of output port level efficiently and fairly. The buffer memory allocation to each of K output port queues is dynamically set to be T_new(t) by Eq.(1). However, in an ATM switch, buffer memory may need to be further divided below the port level. For example, as was mentioned earlier, an output queue may consist of many VCs. If per-VC queuing is adopted, the buffer memory needs to be logically assigned to each individual VC queue as well.

[0054] Another embodiment is described herein where each output queue k has L_kVCs, k=1, 2, . . . , K. The queue length for each VC of output queue k at time t is denoted by Q_kl(t), 1=1, 2, . . . , L_k. One widely adopted buffer management policy requires the buffer memory to be fairly shared among different output queues first (as was have done in the previous section). Then, within each output queue, the allocated memory is further fairly shared among all the VCs to this output port. This presents a multi-level buffer management problem. In this preferred embodiment the techniques of the present invention are used to develop a multi-level dynamic queue threshold scheme to meet the above criteria and in the meantime, to maximize the buffer utilization.

[0055] TP(t) is the dynamic queue threshold for each output queue and TV_k(t) the dynamic queue threshold for each VC queue destined to output port k, k=1, 2, . . . , K. When a cell of VC l to output port k arrives. The dynamic queue thresholds TP(t) and TV_k(t) are computed in a two-step algorithm:

[0056] 1. For the port queue k, $\begin{array}{cc}\mathrm{TP}\left(t\right)=\{\begin{array}{cc}\max \left(Q_k\left(t\right)+1,{\mathrm{TP}}_{\mathrm{old}}\right),& \mathrm{if}Q\left(t\right)<\alpha *B,\\ \max \left({\mathrm{TP}}_{\mathrm{old}}-1,T_m\right),& \mathrm{if}Q\left(t\right)\ge \alpha *B,\end{array}& \left(2\right)\end{array}$

[0057] 2. For the VC queue l of port k, $\begin{array}{cc}{\mathrm{TV}}_k\left(t\right)=\{\begin{array}{cc}\max \left(Q_{\mathrm{kl}}\left(t\right)+1,{\mathrm{TV}}_k^{\mathrm{old}}\right),& \mathrm{if}{Q}_k\left(t\right)<\beta *\mathrm{TP}\left(t\right),\\ \max \left({\mathrm{TV}}_k^{\mathrm{old}}-1,T_m\right),& \mathrm{if}{Q}_k\left(t\right)\ge \beta *\mathrm{TP}\left(t\right),\end{array}& \left(3\right)\end{array}$

[0058] where $Q_k\left(t\right)=\sum _{l=1}^{L_k}{Q}_{\mathrm{kl}}\left(t\right).$

[0059] The parameter β serves the sane purpose as the α does and 0<β≦1.

[0060] The arriving cell is accepted if Q_k(t)<TP(t) and Q_kl(t)<TV_k(t) and Q(t)<B. Otherwise, the cell is blocked. TP(t) and TV_k(t) then update the thresholds TP_oldand TV_old, respectively, whether the cell is accepted or it is discarded.

[0061] The above algorithm provides a dynamic buffer allocation scheme for buffer management at two different levels: port level and VC level. It ensures the fair and maximal sharing of buffer memory at two different levels: first at port level, then at VC level within a port. To elaborate, it is assumed that m out of K output queues are overloaded (i.e., they demand as much buffer as possible) and the rest of output queues are underloaded (i.e., they do not need any buffer for the moment). For the overloaded output queue k, there are n_koverloaded VCs, n_k≦L_k. α=β=1 is set to provide a complete sharing of buffer memory B. Then, according to the algorithm by Eqs.(2) and (3), the buffer allocation for each of m overloaded output queues is B/m, and the buffer allocation for each of n_koverloaded VCs of port k is $\frac{B}{m*n_k}.$

[0062] A skilled artisan will note that the above algorithm can be easily extended to deal multiple-level dynamic buffer allocation problems although only a scheme for a two-level buffer management, which is more common in practice, is presented. On the other hand, if all VCs require the same fair buffer allocation without concerning the fairness among output queues, the scheme is simplified by directly applying the algorithm described earlier to all the VCs.

[0063] Performance Comparisons and Simulation Results

[0064] In this section, the performance of the dynamic threshold scheme and other buffer management schemes are compared through several illustrative examples.

[0065] In the dynamic threshold scheme by Choudhury and Hahne in See A. K. Choudhury and E. L. Hahne, “Dynamic Queue Length Thresholds in a Shared-Memory Packet Switch”, IEEE/ACM Trans. Networking, Vol. 6, No., pp. 130-140, April, 1998, there are certain amount of buffer memory θ left unallocated in steady-state as it is inherent in their scheme: $\theta =\frac{\alpha B}{1+\theta ·S^{\prime }}$

[0066] where S is the number of overloaded queues and θ is a multiplier parameter. While the memory left unallocated would be negligible if there are many overloaded queues or the parameter θ has a very large value, the authors have shown in A. K. Choudhury and E. L. Hahne, “Dynamic Queue Length Thresholds in a Shared-Memory Packet Switch”, IEEB/ACM Trans. Networking, Vol. 6, No., pp. 130-140, April, 1998, that a very large value of θ makes the dynamic control ineffective. On the other hand, with appropriate traffic policing, bandwidth allocation and other control mechanism, it is less likely that many queues, each of which goes to a different output port or line, become congested simultaneously. Therefore, the unutilized amount of memory in θ can be substantial in certain cases. For example, if α=1 for complete sharing and θ=1, a usually good choice, half of the memory would not be allocated when there is only one overload queue.

[0067] In the first example, a buffer memory of 120 cells is shared by queues corresponding to four different output ports. A server of capacity 600 Mbps serves the four port queues in a round-robin fashion. A different source (or VC) feeds each port queue. The first VC is a CBR source with an arrival rate of 310 Mbps. The rest are “on/off” VBR sources with a peak rate of 310 Mbps and different “on” and “off” periods so that the overall system is stable but the overload occurs whenever there are two or more sources are actively sending cells. However, in case of only one active and overloading VC, the algorithm described in Chaudhury et al. allows that VC to take all of the available buffer memory, which are 120 cells. From FIG. 3 it can be seen that using the DT scheme of the present invention, the steady state queue occupancies for each queue are 60 cells, 40 cells and 30 cells when two, three and four VCs are active, respectively. That exactly conforms to their fair shares of buffer memory computed by the algorithm in Chaudhury et al. while the whole buffer memory of 120 cells are being used. Using the DT algorithm in Choudhury et al. the fair shares of buffer memory would be 60 cells, 40 cells, 30 cells and 24 cells, respectively. That results in unused buffer of 50%, 33%, 25% and 2%, respectively.

[0068] For static threshold scheme with the threshold being 60 cells for each port queue, the buffer is 50% under-utilized when there is only one overloading source, and the third and fourth sources cannot gain their fair shares of memory when they become active.

[0069] In the second example, the same buffer memory of 120 cells shared by four VC queues destined to two different output ports. Each VC queue is fed by a different source. The first VC is destined to output port #1 and is an “on/off” VBR source with peak rate 310 Mbps. The other three statistically identical VCs are all destined to output port #2 and are CBR sources with a peak rate of 310 Mbps. Therefore, the VCs to output port #2 always create an overloading situation and need as much available buffer memory as possible. The dynamic buffer-sharing policy has two levels: the two different ports have fair shares of buffers at port levels; within the each port buffer share, different VCs have their fair shares. The dynamic queue threshold scheme of the present invention outlined by Eqs. (2) and (3) is applied. From FIG. 4, it is clear that, when the three VCs to port #2 become active at t=500 (cell time), the system is overloaded, the VC to port #1 gains its fair share of 60 cells for port-level memory allocation and the VCs to port #2 gain the other 60 cells altogether, with each of the three VCs having its fair share of 20 cells for VC-level memory allocation. When the VC to port #1 turns inactive around t=3500 (cell time), its memory allocation of 60 cells is available. Now the three active VCs to port #2 can take all 120 cells of memory at port-level, with each having its fair share of 40 cells for the VC-level. Then, when the VC to port #1 becomes active again, it re-gains its 60 cells for the port-level fair share.

[0070] Conclusion

[0071] A novel dynamic buffer management scheme for shared-memory ATM switches is disclosed. In the same spirits of the buffer management scheme proposed in Choudhury et al., the present invention has been shown to adapt to the changing queue conditions by providing fair buffer memory sharing to on-demand traffic load. The implementation is rather simple as it requests minimum processing power to compute dynamic queue thresholds. In addition, the present invention maximizes the utilization of buffer memory. By adjusting the parameter α in (1), one can control the degree of memory sharing. It is also shown how the dynamic queue threshold algorithm can be applied to develop a multi-level buffer management scheme.

[0072] With the dynamic thresholds, a hierarchical buffer memory partitioning schemes provided. The scheme logically divides and allocates buffer memory in multiple levels. It takes into account the statistical characteristics of traffic and the QoS concerns of service at group and class levels, and ensures the fair and optimal sharing of buffer memory to changing traffic conditions at port and VC levels.

[0073] Other modifications and variations to the invention will be apparent to those skilled in the art from the foregoing disclosure and teachings. Thus, while only certain embodiments of the invention have been specifically described herein, it will be apparent that numerous modifications may be made thereto without departing from the spirit and scope of the invention.