PT116948B - APPARATUS AND METHOD FOR LOAD CONTROL MANAGEMENT IN DISTRIBUTED DATA PROCESSING SYSTEM - Google Patents

Abstract

THE PRESENT INVENTION PROVIDES AN ADMISSION CONTROL SOLUTION (200) FOR A DATA PROCESSING SYSTEM (500), WITH THE ADMISSION OF SERVICE EVENTS (170) AT EACH SERVICE EVENT INTERFACE, CONTROLLED BY A MULTI-LEVEL TOKEN BUCKET, WITH LOAD UNIT TOKENS. EACH ADMITTED SERVICE EVENT CONSUMES A LOAD UNIT TOKEN, WITH THE TOKENS STORED IN THE MULTI-LEVEL TOKEN BUCKET REPRESENTING THE TOTAL PROCESSING CAPACITY AVAILABLE TO THAT SYSTEM NODE. A TOKEN GENERATOR FILLS THE MULTI-TIER TOKEN BUCKET AT THE RATE DETERMINED BY THE CURRENT LOAD RATE LIMIT (240) ALLOWED FOR THE SYSTEM NODE. THE LIMITS (240) ARE CALCULATED AND UPDATED EXTERNALLY BY A CENTRALIZED LOAD MANAGER (510) THAT HAS KNOWLEDGE OF THE OVERALL SYSTEM STRESS LEVEL.

Description

DESCRIPTION

APPARATUS AND METHOD FOR LOAD CONTROL MANAGEMENT IN DISTRIBUTED DATA PROCESSING SYSTEM

FIELD OF INVENTION

The present invention is within the field of load control management for highly distributed and mission-critical data processing systems. In particular, the present invention relates to apparatus and methods for enforcing load rate limits applied upon admission to discrete service events received at the edge of highly distributed and mission-critical data processing systems.

PREVIOUS TECHNIQUE

Token bucketing is an algorithm used in packet-switched networks and can be used to verify that data transmissions (in the form of packets) comply with defined bandwidth and packet flow burst limits.

This algorithm is based on an analogy of a fixed-capacity bucket in which tokens representing a unit of capacity are added at a specific rate. When a packet, request, or event must be checked for compliance with the defined limits, the bucket is inspected to see if it contains enough tokens for the required packet. If so, the appropriate number of tokens are removed from the bucket and the packet is processed. If not, the packet is non-compliant (e.g., there are not enough tokens in the bucket), the contents of the bucket are not changed, and non-compliant packets may be discarded, held for later processing, or even forwarded but marked as low priority.

A compliant packet flow can therefore have an average rate up to the rate at which tokens are added to the bucket, and have a burstiness determined by the depth of the bucket. The basic token bucket algorithm follows the following principles:

1. A token is added to the interval R(rate) times per second;

2. The bucket capacity is B tokens. After it is full, if a new token arrives, it is discarded (overflow);

3. When a packet of weight N arrives, N tokens will be taken from the bucket and will be processed or forwarded;

4. If the bucket has less than the required N tokens, no tokens will be removed from the bucket and the package will be considered non-compliant.

In the long run, the packet rate is limited by R. In other words, the average rate will converge to this value. However, bursts are allowed, taking advantage of some degree of elasticity that the system may have, avoiding discarding all requests above the reference rate R, wasting existing capacity in the system.

For event differentiation and event classes, we need a more sophisticated mechanism like Hierarchical Token Bucket.

Conceptually, the Hierarchical Token Bucket (HTB) is an arbitrary number of basic token buckets (TB) organized in a hierarchy. Each individual TB of the entire HTB will be defined with two parameters: a rate and a ceiling. In HTB, rate means the guaranteed bandwidth available for a given TB and ceiling is short for ceiling, which indicates the maximum bandwidth that the TB can consume. Any bandwidth used between the rate and the ceiling is borrowed from a parent TB. The Hierarchical Token Bucket implements a class-based queuing mechanism typically for the traffic control system and provides the rate and ceiling to allow the user to control the absolute bandwidth for particular classes of traffic, as well as indicate the proportion of bandwidth distribution when extra bandwidth is available (up to the ceiling).

The total protected system capacity and burst elasticity require dynamic variations of the rate (R) and bucket capacity (B). HTB is a suitable approach when we do not have requirements for varying total system capacity and burst degree. HTB has a static burst-level approach that leads to complex burst adaptation, so related runtime adjustments are not feasible. Adapting HTB to allow for sudden increases and variations of total capacity at runtime would be a frequent and resource-intensive activity.

Regarding event classification, not all events discarded in the system's input request flow have the same effect on saving computational resources, and they do not have the same impact on the service being provided. For example, in an application scenario for session event control, systems may receive Initial (I), Intermediate (M) and Final (F) events, which are the packet classes.

If the control policy were to block undifferentiated event classes I, M, and F after the basic token bucket is exhausted, the negative effect would be:

• H - eliminating a final packet would leave sessions without a proper closing event and would waste all the effort made so far with the corresponding initial and all intermediate packets.

• M - dropping an intermediate packet would interrupt a successful session and waste all the effort made so far with the corresponding initial and previous intermediate packets;

• I - discarding an initial packet will not waste any previously completed packet processing, saving resources for currently running session packets;

This situation presents a trade-off between the resource savings of this event drop and the resource waste associated with correctly processed previous session events. In the first bursty stage, the best option is to discard only initial events and not intermediate or final ones, saving resources for the current sessions. The interrupted initial events would create additional unwanted sessions during the stress period. New sessions and initial events would be admitted as the current sessions are terminated and the overall event rate returns to a normal level. In a second stage, when it is not enough to discard the initial events, it is desired to continue to discard them by completing the discarding amount with intermediate events. In this situation, all I events are discarded, as well as some of the M events. A third stage would behave similarly by discarding all I and M events, but only part of F events.

This cannot be achieved with a basic TB (does not support event classes) nor with the HTB approach, as this relies on a weighted priority mechanism. In scenarios where intermediate events (M) should not be discarded while initial events (I) are being processed (class differentiation), HTB addresses the problem with two different buckets (one for each event type) with different bucket rates (R).

However, this would lead to leaf bucket weighting and would not solve the problem described.

This solution aimed to innovatively overcome these problems.

SUMMARY OF THE INVENTION

It is a general object of the present invention to provide means for effective load control of a load-constrained distributed data processing system by developing a novel apparatus and method of operation thereof which are suitable for performing admission control. These and other objects are achieved in accordance with the appended set of claims.

According to one aspect of the present invention, there is provided an admission controller apparatus for limiting the acceptance of service events, at service event interfaces, of a load-constrained distributed data processing system, comprising: an admission blocker unit for performing load rate limit enforcement by executing a multi-level token bucket algorithm; a control interface unit for sending current load rate information and receiving updates to the load rate limit; and, a load token generator unit for generating load unit tokens for the multi-level token bucket.

According to another aspect, the present invention provides a method of admission control for a discrete service event in a distributed data processing system, comprising the steps of: i.) Identifying the type of service event, to apply acceptance priority rules; said priority rules are implicitly applied when sending the decision to forward the event to the multi-level token bucket algorithm. In other words, after a first step of classifying the event, a certain amount of tokens will be collected in the corresponding level of the multi-level token bucket, and therefore, the lower priority levels will see tokens depleted faster than the others; ii.) checking the load rate compliance for the service event type, using a multi-level token bucket algorithm to check compliance with defined load rate limits; iii.) performing acceptance of the service event according to the load rate compliance assessment.

According to another aspect of the present invention, management of a load rate limiter for an admission controller, at a service event interface, in distributed data processing systems, is disclosed, comprising the steps of: i.) receiving load rate limit updates to enforce a load rate limit according to the current stress level of the distributed data processing system; ii.) determining the rate of the token generator to generate load tokens at the correct rate; and, iii.) calculating and sending the current load rate to inform a centralized load manager of the level of load that is occurring.

According to this admission controller apparatus and its admission control method including load rate management, admission control of service events at service event interfaces to a distributed data processing system can be performed effectively and efficiently based on received load rate threshold updates that allow immediate actions on rejecting events under load stress conditions.

DESCRIPTION OF FIGURES

Figure 1 illustrates a multi-level token bucket composition in accordance with the present invention. The reference signals represent:

100 - Load capacity bucket token;

110 - Cargo token units;

112 - Forwarding service event;

113 - Disposal service event

120 - fee for adding load token units;

130 - Current available load capacity level;

140 - Minimum level of charge token units;

150 - disconnect flow;

160 - service event streams;

170 - Service event;

180 - Service event interface;

190 - Maximum available load capacity level;

Figure 2 represents a high-level block diagram of the admission controller apparatus according to the present invention. The reference signals represent:

170 - Service event;

180 - Service Events Interface;

200 - Admission control device;

210 - Intake blocking unit;

220 - Control interface unit;

230 - Load token generator;

240 - Charge rate limits and current charge rate information.

Figure 3 is a flowchart describing an admission control method for discrete events in a distributed data processing system according to the present invention. The reference signals represent:

S300 - Identification of the type of service event received;

S310 - Verification of load compliance for service event based on service event type;

S320 - Execution of acceptance control for the service event.

Figure 4 is a flowchart describing the load rate management for an admission controller in a distributed data processing system according to the present invention. The reference signals represent:

S400 - Receive load rate limit updates;

S410 - Determine the token generator fee;

S420 - Calculating current input load rate.

Figure 5 shows an admission control solution in a distributed data processing system according to the present invention. The reference signals represent:

170 - Service event;

200 - intake control device;

240 - Charge rate limits and current charge rate;

500 - Data processing system;

510 - external central load manager.

DETAILED DESCRIPTION

The present invention provides an apparatus for controlling the admission of discrete service events for load control at service event interfaces in distributed data processing systems, which is based on a multi-level token bucket algorithm, which is used to limit the number of service events with different priorities at a service event interface that will be accepted for processing. In particular, the multi-level token bucket algorithm will be used to supervise and ensure the enforcement of the load rate limits provided for the service event interface.

Token bucketing is an algorithm that has proven effective and reliable in many packet switching and telecommunications network scenarios to verify and enforce the compliance of packet data transmissions with defined bandwidth and burst limits. On the other hand, controlling the available processing capacity of a system is fully equivalent to controlling the available bandwidth of a data transmission stream, and this equivalence arises from the fact that it is possible to draw a complete analogy between the two mechanisms: first, a service event is equivalent to a data packet; second, an availability of processing capacity is equivalent to an availability of bandwidth; and finally, a unit of processing capacity is equivalent to a packet size.

Thus, based on the equivalence of both types of control, it is possible to use the token bucket algorithm approach in a mechanism to control the available processing capacity of the system is also an efficient and reliable mechanism.

Fig. 1 illustrates the hypothetical use of a token bucket algorithm approach applied to a mechanism for controlling the available processing capacity of a system through the use of load unit tokens (units of known available processing capacity) managed by a token bucket. This particular use case of the token bucket algorithm, as shown in Fig. 1, is based on an analogy of a known load capacity token bucket 100, in which tokens, representing a load unit 110 that is available to be used by a service event 170 arriving at a service event interface 180, are added to the token bucket at a rate 120 that may change based on updates from an external source, as shown in Fig. 1.

According to Fig. 1, the token bucket 100 may manage the current available load capacity level 130 assigned to a service event interface 180 of a distributed data processing system, via the stored load unit tokens 110 up to a maximum available load capacity level 190. Thus, this current available load capacity level 130 represents the undifferentiated system load capacity that may be shared, at any given time, among multiple service event streams 160 existing on a service event interface, as shown in Fig. 1.

According to Fig. 1, it is possible to expand the traditional token bucket algorithm into a multi-level token bucket algorithm to allow simultaneous and differentiated control of multiple service event streams 160 that share the same system processing capacity controlled by the multi-level token bucket 100. In particular, it is possible to limit, for each service event stream 160, the load used to a fraction of that allocated to the service event interface 180, by setting a minimum level of payload token units 140 to allow the use of payload token units 110. Furthermore, it is possible to open or close the transmission of a service event stream via the shut down flow 150.

Furthermore, Fig. 1 shows that an acceptance priority mechanism for service events can be implemented based on the multi-level token bucket 100 functionality through the use of minimum payload token unit levels 140. In particular, each service event stream is associated with a specific service event type for which a specific threshold (minimum payload token unit level) 140 is configured in the multi-level token bucket 100. In this mechanism, a payload token unit is only available for use by a service event of a specific service event type if the current available payload capacity level 130 is higher than the threshold 140 configured for that specific service event type. Thus, setting different thresholds 140 for the service event streams 160 implicitly sets different acceptance priorities for service events of those service event types, with threshold 140 having the highest value implicitly of the lowest priority and threshold 140 having the lowest value of the highest priority.

The multi-tier token bucket, to be effective in resolving admission control in a scenario with the intermittent nature of multiple service event interfaces competing for use of the available load capacity of a distributed data processing system, needs to adjust its rate of addition 120 of payload token units 110 dynamically through updates from an external load manager. In addition, the multi-tier token bucket 100, to keep the acceptance priority mechanism working properly, needs to update the thresholds (minimum levels of payload token units) 140 in proportion to the load rate limit updates.

The multi-level token bucket algorithm enables efficient admission control of discrete service events of different types that share the same processing capacity. It also provides effective admission control for distributed systems by enabling continuous updates of load rate limits from external sources.

IMPLEMENTATION MODELS

Embodiment model 1: Admission control device

In the following, an embodiment of the present invention relating to an intake controller apparatus will be described with reference to Fig. 2.

Fig. 2 shows an admission controller 200 for controlling access to service events 170 on a service event interface 180 of a distributed data processing system according to the present invention and comprises, as shown in Fig. 2, an admission blocking unit 210, a control interface unit 220 and a payload token generator unit 230. The admission blocking unit 210, shown in Fig. 2, performs admission control of discrete service events on a service event reception interface in order to perform the application of a load rate limit. The admission control unit 210 uses the payload tokens generated on the payload token generator unit 230 in conjunction with its own parameterization to apply appropriate admission control to the load stress levels identified externally by the operational management of distributed data processing systems. Such parameterization is necessary for the operation of the admission blocking unit 210 and may relate to a definition of the total size/capacity of a token bucket 190, as well as the various output levels 150 at which each event type removes tokens.

The control interface unit 220, shown in Fig. 2, receives the allowed load rate limit updates, which are calculated remotely by an external central load manager 510. The control interface unit 220, shown in Fig. 2, also sends to the external central load manager 510 the current effective load rate and, optionally, the nominal load rate. The effective load rate is based on the arrival rate/request rate for processing events in the system. The purpose of its calculation is related to the need for central adjustment of the load rate limits parameter. This parameter will affect the load token generation unit (230), increasing or decreasing the rate of token generation in the multi-tier token bucket. Typically, this limit will be reduced to rebalance capacity in the context of a distributed system. Likewise, it will be increased when there is a request for more capacity within the initial, statically parameterized limits. The nominal rate, in turn, represents a static/initial parameter and constitutes an absolute maximum ceiling differentiated by the apparatus (200). The token generator unit 230, shown in Fig. 2, generates charge tokens at the rate determined by the charge rate threshold updates. The token generator's pacing may be configured to produce a single or a burst of charge unit tokens on each clock tick, but on average the generation rate of charge unit tokens will always be in accordance with the received charge rate threshold.

Implementation model 2: Admission control method

Next, an embodiment of the present invention related to an admission control method will be described with reference to Fig. 3.

Fig. 3 shows a flowchart describing an admission control method for discrete service events in a distributed data processing system in accordance with this invention.

In a first step S300, received discrete service events are analyzed to identify the type of service event according to the set of those allowed to be accepted.

In the next step S310, discrete service events are checked for potential violation of the load rate limit based on the service event type. The load rate violation check is achieved using a multi-level token bucket algorithm that uses the current load rate limit and a parameterization of the data processing system. This parameterization, in addition to the total capacity of the token bucket 190 and the various output levels 150, also needs the classification criteria of the various event types and the number of tokens that each type uses.

In the next step S320, if the load compliance assessment is passed, the discrete event is accepted and forwarded to be processed by the distributed data processing system.

Embodiment model 3: Load rate limiter management method

Next, an embodiment of the present invention related to a method of managing the load rate limiter will be described with respect to Fig. 4.

Fig. 4 shows a flowchart describing a method of managing the load rate for an admission controller in distributed data processing systems in accordance with this invention.

In a first step S400, load rate limits are received from an external load manager to be used to update the production rate of load unit tokens according to the stress level of the distributed data processing system.

In the next step S410, the token generating unit 230, shown in Fig. 2, adjusts its pacing to the new received charge rate limit. The pacing is calculated based on the received charge rate limit and the setting of the single or burst charge unit token production pacing at each clock tick.

In the next step S420, the current input load rate is determined to provide feedback to an external load manager in order to receive back load rate limits adjusted to the current stress level.

Admission control solution

In the following, an embodiment of the present invention related to an admission control solution will be described with reference to Fig. 5.

According to Fig. 5, the admission control solution comprises the admission controller apparatus 200, which uses the admission control and load rate limiter management methods as described above in a combined manner. In particular, the admission controller apparatus 200 is connected to an external central load manager 510 to receive the allowed load rate limit updates and to send the current effective load rate 240 and, optionally, the nominal load rate.

Additionally, for distributed systems scenarios, there will be multiple instances of the admission controller appliance 200 operating independently.

As will be clear to one skilled in the art, the present invention is not to be limited to the embodiments described herein, and a number of modifications are possible that remain within the scope of the present invention.

It is clear that the preferred embodiment models shown above can be combined in the different possible forms, and the repetition of all these combinations is avoided here.

Claims (11)

1. An admission controller apparatus (200) configured to control access to service events on a service event interface of a distributed data processing system, characterized by comprising: - an admission blocking unit (210) comprising processing means adapted to perform admission control of discrete service events based on a load rate limit of a service event reception interface of a service event interface (180); - a control interface unit (220) comprising processing means and communication means adapted to establish a bidirectional communication link with an external central load manager (510) for the purpose of receiving permitted load rate limit updates; and a - Load token generating unit (230) comprising processing means adapted to generate load unit tokens at a rate determined by load rate limit updates, wherein, - The admission blocker unit (210) being configured to use the load unit tokens generated by the load token generator unit (230) to execute a multi-level token bucket algorithm in conjunction with its own parameterization to apply admission control appropriate to load stress levels of the distributed data processing system. 2. The apparatus (200) of claim 1, wherein the allowable load rate limit updates are calculated remotely by the external central load manager (510). 3. The apparatus (200) according to any one of the preceding claims, characterized in that the number of load unit tokens generated by the load token generating unit (230) is proportional to the load rate limit of a service event. 4. The apparatus (200) according to any one of the preceding claims, characterized in that the control interface unit (220) is further configured to calculate a current effective charge rate and send to the external central charge manager (510) said current effective charge rate. 5. The apparatus (200) of claim 4, wherein the control interface unit (220) is further configured to calculate a nominal rate and send to the external central load manager (510) said current nominal rate. 6. The apparatus (200) according to any one of the preceding claims, characterized in that the charge token generator (230) is configured to generate a single or a burst of charge unit tokens. 7. The method for performing admission control in a distributed data processing system, using the admission controller apparatus (200) of claims 1 to 6, and comprising the following steps: i. discrete service events are received and analyzed by the admission blocking unit (210) in order to identify the type of service event according to a set of service event types allowed to be accepted; ii. the accepted discrete service events undergo a load compliance assessment performed by the admission blocking unit (210) in order to check whether there is a violation of a load rate limit based on the respective service event type; said load rate limit being received by the control interface unit (220); iii. discrete service events that do not violate the load rate limit are accepted and forwarded to be processed by the distributed data processing system. 8. The method of claim 7, wherein updating the load rate limit is performed according to the following steps: i. load rate limits are received by the control interface unit (220) from an external load manager according to a stress level of the distributed data processing system; ii. the load rate limit updates are calculated by the control interface unit (220) based on the received load rate limits; iii. a token generator rate in the load token generator unit (230) is determined by adjusting a load unit token generation rate depending on load rate limit updates calculated by the control interface unit (220) in accordance with the load rate limits received from the external load manager; iv. a current input load rate is calculated by the control interface unit (220), which sends response information to the external load manager in order to receive back load rate limits adjusted for the current stress level of the distributed data processing system. 9. The method of claim 8, wherein the rate of generation of charge unit tokens by the charge token generator (230) is further dependent on a single or burst rate of production of charge unit tokens at each clock tick. 10. The method according to any one of the preceding claims 7 to 9, characterized in that the load rate violation check is performed by the admission blocking unit (210) executing a multi-level token bucket algorithm. 11. The method of claim 10, wherein the multi-token algorithm uses the following parameters: a load rate limit and a parameterization of the data processing system.