Hierarchical dynamic buffer management system and method

[0002] Invention relates to electronic storage, particularly to hierarchical buffer systems.

[0003] Conventional digital electronics systems employ various storage structures, including buffers, queues, caches, or other similar memory devices. More recently, especially for distributed networking and applications, such as those applications for enabling high-speed transmission, processing, and storage of so-called Internet or related digital data or signaling traffic, buffers and similar electronic repositories are increasingly used as temporary storage, for example, to avoid or otherwise manage congestion of traffic flow of packets, cells, frames or other data units through a network gateway.

[0004] Various approaches are used to police gateway queuing of traffic load at given times. In particular, with buffer structures being used to hold temporary excess traffic load at a gateway, numerous buffer management algorithms are proposed, such as last packet discard (i.e., “drop tail” approach), randomization (i.e., “early random drop” (ERD), “random early detection” (RED), “flow random early drop” (FRED)), as discussed in further detail in references cited in this patent application, which are hereby incorporated by reference as appropriate.

[0005] However, such present approaches are limited in optimizing data throughput and maintaining fairness amongst different flows, particularly for processing arriving data units for allocation in hierarchical buffer systems. Accordingly, an improved solution is required to optimize data throughput and storage.

[0006] Invention resides in a multi-level buffer system and/or method for managing buffer resources to reduce or eliminate network congestion, particularly by dynamically allocating storage resources to arriving data units according to hierarchical acceptance criteria. Moreover, stored data units are retrievable according to hierarchical schedule.

[0007] Acceptance criteria may comprise minimum and/or maximum threshold values, which are pre-specified or dynamically computed, and may be determined from system resource and storage availability. Data units are accepted for allocated buffer storage upon dynamically-determined satisfaction of certain hierarchically-based acceptance criteria. Such criteria may be determined from reserved minimum buffer length, calculated maximum buffer length, or random early discard-type algorithm applied separately to each buffer level.

[0008] FIG. 1A is a general system block diagram of a hierarchical buffer system for implementing a preferred embodiment of the present invention. FIG. 1B is a diagram for illustrating functional aspects of the present invention.

[0009] Generally, a preferred implementation accomplishes dynamic hierarchical or non-hierarchical buffering and management thereof using multiple-level buffer, queue, or similar digital repository sub-systems, each such buffer system being assigned or otherwise associated with certain predetermined or dynamically calculated acceptance criteria, such as minimum and/or maximum threshold values for accepting one or more data units, such as packets, cells, frames, or other network-transmitted or accessible digital signals, arriving from or through a network gateway, port, or other network-coupled node.

[0010] Additionally, a processor, computer, controller, logic circuit, software program application, or other electronically programmable device, state machine, or equivalent functional module is provided for dynamically managing one or more buffers for storing and/or retrieving one or more arriving data units in single or multi-level buffer sub-systems or systems. Preferably, each arriving data unit is stored once in the buffer system, but associated with one or more hierarchical or modular levels, as described herein.

[0011] Such processor functionality may serve to execute instructions or cause to determine acceptance criteria for an arriving data unit and/or its corresponding hierarchical or modular level or queue according to one or more pre-determined or dynamically calculated values, which represent certain buffer system resources or conditions, such as system loading or available storage, preferably respectively for each hierarchy level or queue.

[0012] Additionally, the processor may execute instructions or cause to retrieve separately one or more data units from certain level buffer locations, preferably according to a modular or hierarchically-based schedule. In such retrieval manner, the processor may execute instructions or cause to generate separate traffic flows over different data paths or links as well as different or overlapping times, as appropriate to optimize data processing and reduce network congestion.

[0013] Preferably, in one embodiment of the present invention, arriving data unit(s) are preferably stored once in the buffer system, being accepted and accessible for available storage allocation in different queues or buffer subsystems only when each and all level acceptance criteria or specified thresholds are determined by the processor to be satisfied.

[0014] Hence, to enable operation of a preferred embodiment for dynamically buffering arriving data units, a network gateway such as a router, switch, or other interconnect port is accessible to a level N repository associated with minimum and/or maximum thresholds, and a next-hierarchically higher or lower level N+1 repository associated with minimum and/or maximum thresholds. Levels N, N+1 may be non-hierarchically related.

[0015] Then, one or more data units arrive or is electronically accessible at the network gateway for data or signal processing such received data unit(s) by a programmed processor, controller, computer, or other functionally equivalent logic circuit, state machine, or executable software code.

[0016] Preferably, acceptance criteria are pre-specified or dynamically determined to allocate certain buffer storage locations to arriving data unit(s). For example, minimum and/or maximum threshold values are provided by a processor for the level N repository and/or the level N+1 repository, such that buffer storage locations in the level N repository and/or the level N+1 repository are allocated to one or more received data units.

[0017] Optionally, such provided minimum and maximum threshold values for level N and/or level N+1 repositor(ies) are predetermined or calculated dynamically by the processor according to prior, current, and/or expected system loading or availability of the level N and/or level N+1 repositories.

[0018] As specified in further detail herein, acceptance criteria may be determined by calculating a buffer length associated with arriving data unit(s) or its/their corresponding hierarchical level or queue. In particular, a data unit is always accepted if the buffer length is less than a minimum value. This requires a minimum number of buffer locations to be reserved. To accept the data unit into the non-reserved locations, the buffer length has to be less than a dynamic maximum buffer length (b_{max i}) substantially according to the following formula:

[0019] b_{max i}=b_{min i}+α_iF(FB)

[0020] where: b_{min i}represents a minimum reserved buffer length,

[0021] FB represents a free storage size,

[0022] α_irepresents a number of non-negative values less than or equal to 1, and

[0023] F represents a function for sharing free storage size.

[0024] In general, F may be any non-negative, non-decreasing functions.

[0025] Moreover, as specified in further detail herein, acceptance criteria may be determined by applying a random early discard (RED)-type calculation to the buffer systems at one or more levels.

[0026] Upon satisfying the acceptance criteria and the allocation of buffer storage locations to certain arriving data units, then, the data units are accordingly stored in the allocated locations. Each data unit may be stored once in the overall buffer system, but accessible or associated with multiple modular or hierarchy levels.

[0027] Subsequently, such stored data units may be retrieved by the processor, preferably according to a hierarchical retrieval schedule. In such hierarchical manner, the processor may execute instructions or otherwise cause the generation of hierarchically-based traffic flows, e.g., where certain retrieved data unit is transmitted as part of a digital stream or network traffic flow which is associated with one or more hierarchical level or queue.

[0028] Referring to FIG. 1A general system block diagram, hierarchical buffer system 10 is shown, preferably cooperating functionally with one or more processor, computer, or controller 8, having digital memory for storing executable programs or other data files. Hierarchical buffer system 10 couples 6 to one or more network gateways or other accessible port for receiving, sending, or otherwise communicating to access certain digital data units or signals for processing, storage, or temporary buffer management and congestion avoidance as specified herein.

[0029] Hierarchical or modular buffer system 10 may include one or more levels or queues corresponding to one or more hierarchical levels or functional partitions. Here, three levels 10, 12, 14 are shown, whereby level 010 represents a complete, general buffer system. Generally, level N system may include one or more schedulers 18, 20 and a number of level N+1 buffer systems or subsystems, which are managed by scheduling software or circuit logic. If N equals the top level, then the buffer system does not necessarily employ a scheduler, and data may be stored in a First-In-First-Out(FIFO)-type queue.

[0030] In such a hierarchical or modular configuration, one or more storage systems may be configured, for example, with N levels of buffers. Hence, a buffer system at level-i, for instance, may be included in one buffer system at level i−1, for i between 1 and N inclusively. Furthermore, a level-k buffer system may contain one or more level k+1 buffer system. Preferably, buffer assignments are configurable. Note that level-0 refers to the entire storage system.

[0031] Data units, either as an Internet Protocol (IP) packet, Asynchronous Transfer Mode (ATM) cell, or frame, are stored preferably only once in the entire buffer system 10. Level N scheduler decides from which level N+1 buffer system to retrieve the data unit for transmission. If N+1 is not the highest level buffer system, then the level N+1 scheduler within a selected buffer system decides among its buffer subsystems from which to retrieve data unit(s).

[0032] The foregoing hierarchical buffer management process is repeatable until the highest level buffer is reached. Then, the data unit at the head of the queue is retrieved and transmitted out of the buffer system. Buffer length information of each buffer system is maintained in storage. Preferably, the following formula applies for determining buffer length:

[0033] B_Nⁱ=Σ_kB_N+1^k, kεS_Nⁱ

[0034] where: B_Nⁱrepresents queue length of“i-th” buffer system at level “N”; and

[0035] S_Nⁱrepresents the set of level N+1 buffer system in the i-th level N buffer system.

[0036] In one implementation of the preferred embodiment, a so-called dynamic maximum with minimum reservation (DMMR) scheme may be employed to improve on congestion avoidance. To guarantee that the data loss probability is less than a specified level, and to isolate interaction from different streams of data units, a buffer system may reserve minimum and set maximum with each buffer system. A fixed minimum is generally sufficient to guarantee minimal quality requirements. However, a fixed maximum may penalize the buffer management system unnecessarily, while other flows may not be using the buffer system. Thus, a dynamic maximum approach is preferred.

[0037] Regarding single buffer systems, storage is allocated generally when buffer systems at all selected levels accept data unit(s). Storage is allocated if buffer length b_{len i}is less than reserved minimum, b_{min i}irrespective of system loading. When buffer length is larger than minimum, then storage is allocated only if buffer length is less than dynamic maximum, b_{max i}. The following formula is used to calculate dynamic maximum buffer usage of each buffer system:

[0038] b_{max i}=b_{min i}+α_iF(FB)

[0039] where b_{min i}represents a minimum reserved buffer length,

[0040] FB represents a free storage size,

[0041] α_irepresents a number of non-negative values less than or equal to 1, and

[0042] F represents a function for sharing free storage size.

[0043] In general, F may be any non-negative, non-decreasing function(s).

[0044] Note that identity function may be used for F. In this case, value of α_iis used to weight different traffic classes. In systems with a small number of buffer systems, such assumptions are sufficient. But a traffic class with a smaller α_imay be penalized, even when the system is lightly loaded. Such inefficiency is apparent when the system has a large number of queues. Here, the range of α_ivalues is chosen to be relatively small to bound per-buffer system maximum. Note that despite free buffers being available, low-priority class traffic may be discarded unnecessarily. Since α_itypically has a relatively coarse range, it may be insufficient to support prioritizing traffic classes and a large number of queues.

[0045] For illustration, the following function serves to improve performance over the identity function. FIG. 1B illustrates functional aspects. Two, parameters characterize F: threshold, T_j, and slope m_j. Together with the α_iparameter, the dynamic maximum is determined as follows: choose the value of α_ito bound maximum for group of buffer systems, and individual (T_j, m_j) values for different buffer systems within the group. Hence, the larger the value of both (T_j, m_j), then the lower priority of a class. If free storage is larger than, say maximum T_j, all classes are treated equally. As free storage size decreases, different classes are affected differently. If threshold T_jis zero, the function reduces to the identify function. Note on identity portion 22 of diagram curve, essentially no users of the buffer system are penalized.

[0046] Following logical steps generally illustrate preferred methodology for implementing DMMR algorithm described herein:

[0047] 1. Data unit (e.g., packet or cell) arrives at buffer or storage system with N buffer levels and is classified to be stored in buffer sequence, b_N, b_N−1, b_N−2, . . . , b₁, b₀. Note: b_iis contained in b_i−1, for i between N and 1; and b₀represents entire storage system.

[0048] 2. For each buffer system b_i,

[0049] 3. If buffer length of b_iis less than associated minimum, then buffer system b_ican accept packet or cell, else,

[0050] 4. If buffer length of is less than dynamic maximum, then buffer system b_ican accept packet or cell, else,

[0051] 5. Buffer system b_i, cannot accept packet or cell.

[0052] 6. If all buffer systems b_N, b_N−1, b_N−2, . . . , b₁, b₀can accept packet or cell, then packet or cell is accepted to storage system.

[0053] Preferably, dynamic maximum is calculated as follows:

[0054] b_{max i}=b_{min i}+α_iF(FB)

[0055] where b_{min i}represents a minimum buffer length,

[0056] FB represents a free storage size,

[0057] α_irepresents a number of non-negative values less than or equal to 1, and

[0058] F represents a function for sharing free storage size.

[0059] (F function sample is shown in FIG. 1B.)

[0060] In another implementation of the preferred embodiment, a so-called queue-protected random early discard (QRED) scheme may be employed to improve further on congestion avoidance. This algorithm applies to multi-level buffer system described herein.

[0061] Generally, conventional RED algorithm does not depend on particular scheduling scheme used, and serves as an admission control mechanism. According to RED algorithm, average buffer length (b_ave) is measured. If b_aveis below minimum, min_th, then packet is accepted. If packet is above maximum, max_th, then packet is discarded. When b_aveis between (min_th, max_th), packet is discarded according to a probability P_b, where:

[0062] p_b=max_p[(q_ave−min_th)/(max_th−min_th)]

[0063] and max_pis the maximum drop probability. This scheme introduces randomness into buffer system and de-synchronizes different network data sources. However, conventional RED approach is insufficient to protect weak flows, i.e., sources that do not send data often, and isolate aggressive sources. Furthermore, other conventional approach Flow RED (FRED) is also insufficient and achieves flow level isolation by performing flow detection and packet counting, which is a costly process.

[0064] A preferred embodiment supports flow level protection by providing the hierarchical buffer system described herein, whereby traffic is isolated and the RED technique may be applied at each hierarchy level or queue. Hence, in the multi-level hierarchical buffer system described earlier, the total number of higher level buffer systems may be large, whereas lower level buffer systems may be much smaller. If the RED algorithm is maintained separately at all levels, then a large number of buffer averages is maintained.

[0065] For general RED calculation, if average queue length value is determined to be between specified minimum and maximum values, then received packet is discarded with given probability. Also, if such average value is determined to be less than minimum value, then received packet is admitted. But, if such average value is determined to be larger than maximum value, then received packet may be discarded.

[0066] Following describes 3-level buffer system (i.e., level 0, 1, and 2); however, technique applies to buffer system with more levels. Preferred algorithm applies averaging technique on level 1 buffer systems. Dynamic maximum threshold computation described earlier may be applied to multi-level buffer system described herein. Such maximum may be fixed or dynamic. Averages on all level-1 buffer lengths are maintained. Threshold, T_L2ⁱ, is specified for all level 2 buffer system i.

[0067] When data unit arrives for possible admission to i-th level 2 buffer system, RED separately applies, preferably under following conditions:

[0068] 1. If average buffer length of level 1 buffer system that i-th level 2 buffer system belongs is larger than RED minimum threshold; and

[0069] 2. Instantaneous buffer length of i-th level 2 buffer system is larger than T_L2¹.

[0070] If instantaneous buffer length of i-th level 2 buffer system is larger than computed dynamic maximum of level 2 i-th buffer system or instantaneous buffer length of level 1 buffer system which i-th level 2 buffer system belongs to is larger than dynamic maximum of level 1 buffer system, then data unit is discarded. Dynamic maximum may be set as fixed or calculated dynamically.

[0071] Present improved algorithm offers protection on level 2 buffer system, but without average calculation. Since dynamic maximum is calculated in fixed or variable manner and available at level 2 buffer systems, aggressive source usage is also limited.

[0072] Following logical steps generally illustrate preferred methodology for implementing QRED algorithm for buffer storage system with 3 buffer levels described herein:

[0073] 1. Time average of buffer length of b₁is computed.

[0074] 2. Data unit (e.g., packet or cell) arrives at storage system with 3 buffer levels, and classified into buffer sequence, b₂, b₁, b₀. Note: b₂is contained in b₁, and b₀represents entire storage system.

[0075] 3. If buffer length of b₂is less than associated minimum threshold, then random early discard (RED) is not triggered, else,

[0076] 4. If buffer length of b₂is larger than dynamic maximum, then discard packet or cell, else,

[0077] 5. If instantaneous buffer length of b₁is larger than dynamic (or fixed) maximum, then discard packet or cell, else,

[0078] 6. Activate RED computation:

[0079] 7. If average buffer length of b₁is below minimum, min_th, then packet is accepted. If packet is above maximum, max_th, then packet is discarded. When average buffer length of b_1,is between (min_th, max_th), packet is discarded according to probability p_b, where:

[0080] p_b=max_p[(q_ave−min_th)/(max_th−min_th)]

[0081] and max_pis maximum drop probability.

[0082] Preferably, dynamic maximum is calculated as follows:

[0083] b_{max i}=b_{min i}+α_iF(FB)

[0084] where b_{min i}represents a minimum buffer length,

[0085] FB represents a free storage size,

[0086] α_irepresents a number of non-negative values less than or equal to 1, and

[0087] F represents a function for sharing free storage size.

[0088] (F function sample is shown in FIG. 1B.)

[0089] Note that preferred QRED calculation procedure applies to hierarchical queuing structure, as described herein. For example, in 2-level system, if queue length in designated high level is determined to be less than specified threshold, then received packet is accepted. Otherwise, RED applicability depends on designated low-level queue average.

[0090] Foregoing described embodiments of the invention are provided as illustrations and descriptions. They are not intended to limit the invention to precise form described. In particular, Applicant contemplates that functional implementation of invention described herein may be implemented equivalently in hardware, software, firmware, and/or other available functional components or building blocks. Other variations and non-hierarchical embodiments are possible in light of above teachings, and it is thus intended that the scope of invention not be limited by this Detailed Description, but rather by Claims following.