Method and system for scheduling data selection for transmission over data network

FIELD: information technology.

SUBSTANCE: system for scheduling data selection for transmission in a data network includes a plurality of daughter elements as well as a credit allocator and a transmission selector. The transmission selector is communicatively connected to the credit allocator, wherein each credit can be used to transmit data. The credit allocator operates to provide credits to one of allowable daughter elements and daughter elements having a negative credit counter. The credit allocator also operates to maintain a credit balance which represents the available total volume of unallocated credits, and subtracts the provided credits from the credit balance. The transmission selector operates to select one allowable and operable daughter element for extraction from a queue and add credits to the credit balance in accordance with the amount of data selected for extraction from the queue.

EFFECT: improved queuing using weight coefficients based on reverse management of credits which can be used in case of traffic with controlled exchange rate.

19 cl, 13 dwg

The technical FIELD TO WHICH the INVENTION RELATES.

The present invention in General relates to a method and system for fair Queuing using the weighting coefficients in the presence of traffic with variable speed metabolism and, more specifically, to a method and system that provides fair Queuing using weights for traffic managed on the basis of frames, and enable restrictions exchange rate and the guaranteed rate of exchange for the children competing in the scheduler fair Queuing using the weighting coefficients.

BACKGROUND of INVENTION

Each computer and each data network carrying data packets should include planning, to ensure the promotion of traffic on the network at a certain speed. At any given time in the network can be hundreds of thousands and even millions of compounds containing data queue awaiting transmission over the network. Requires some planning mechanism that allows network elements to process these data queues in a fair and timely manner.

Usually schedulers interact with data queues for scheduling transmission of data over the network. Planners mouthbut hierarchical - selected child may also be a planner, who must make a choice among its children. The scheduler determines the transmission data of the valid data queues or from other valid child schedulers with available data. In the General case, a separate process places the data in the queue, but you mentioned a separate process associated with the planning, in the sense that it announces the availability of the data or the validity of the child. Planners periodically or upon request choose a child process with data available from which to transfer data. Hierarchically scheduler organizes the transfer of data from the selected queue.

1 shows a data transmission system 10, the corresponding conventional technology, a system that includes the planning process 12, where the route data includes a number of queues 14a, 14b, 14C, 14d and 14 (which are collectively designated as the data queue 14) and multiplexers 16A, 16b (which are collectively designated as the multiplexer 16). Despite the fact that the multiplexer is shown in figure 1 in the form of a physical device in a conventional scalable implementation of multiplexers do not physically exist, but are implied by the choice of the scheduler queue data 14 for transmission. The planning process is of 12 may choose from any data queue 14, having data available ("DA" - "DD"); however, due to the hierarchical nature of the implementation of the planning process 12 must ask the child scheduler 18 to select from the queue data 14d and data queues may 14. Then the child scheduler 18 selects the appropriate data queue 14d, may 14. In this example, the planning process 12 may select data queues 14a, 14b and 14C directly.

One of the processes fair Queuing using the weighting factors disclosed in U.S. patent No. 7.373.420 issued Lyon (hereinafter "420 patent"), the full content of which is incorporated herein by reference. Figure 2 shows the process fair Queuing using the weighting coefficients in accordance with the ' 420 patent", which includes a feedback system loan management, where to determine the queue that you want to "lend", are assigned weights. In principle, the scheduler 20 for fair Queuing using the weighting coefficients on the basis of the reverse loan management ("WFQ-ICM") involves two complementary processes: allocator loans WFQ 22 and the transmission selector 24. The transmission selector 24 generally operates in a cyclical manner, where each child process with data and have positive credit, ucet right to transfer the data on the queue.

The lending process 22 provides loans to child elements, current credits are less than the amount of available data ("ADA") for that child. The volume of credits that each child scored at any given moment, is tracked in the database of the credit status of the child elements 26. The volume of credits each child element never exceeds ADA that child. At any time a child element has a loan smaller than the ADA, and is included in the dispenser 22 credits when competing for extra credit.

The transmission selector 24 selects data child elements with a positive counter loan. When the child passes the data, credits are deducted from its current amount of credit database of the credit status of the child elements 26 and returned to the distributor 22 credits for re-distribution to other children with ADA greater than the number of credits. The dispenser 22 credits provides loans at the same speed with which child elements are spending credits (i.e., the rest is missing), therefore, a key requirement of the WFQ scheduler-ICM 20 is that the system needs to know at each moment of time the amount of data of each child element that is available for transmission is. This requirement prevents a situation when the child is deprived of the right to transmit data, although they, by implementing the processes overlap for determining eligibility for transfer on the basis of practically possible transmission speed. In principle, restrictions on the transfer speed can cause the child process to terminate the transfer of or to be no data available for the parent scheduler. This restriction also leads to a significant increase in the load on a hierarchical schedulers, when ADA includes all subsequent turns, regardless of the number of hierarchy levels is required for effective binding of the planning processes between planning levels.

Thus, you need a method, system and device for fair Queuing using weights based on inverse control credits that can be used with graphics with adjustable baud rate.

BRIEF description of the INVENTION

The present invention provides a method and system for transmission in the data transmission network on the basis of the admissibility of the child elements and the allocation of credits. In the General case the scheduler for fair Queuing using the weighting coefficients on the basis of the reverse loan management can IP olsavica in the presence of traffic with adjustable baud rate, allowing you to enable constraints exchange rate and the guaranteed rate of exchange for the children competing in the scheduler fair Queuing using the weighting coefficients.

In accordance with one aspect of the present invention, a system for scheduling data transmission in a data network includes a dispenser loans and the selector gear. The data network includes many child elements. The transmission selector is associated with the dispenser loans. The dispenser loans operates to provide loans, at least one valid child element and the child element with a negative count of the loan. Each credit can be used for data transmission. In addition, the dispenser loans operates in order to maintain a credit balance represents the total amount of Unallocated credits, supports the fair value of loans between the child elements and subtracts the loans from the credit balance. The transmission selector operates to select at least one valid and workable child element to retrieve from the queue, select a valid and workable child in you is the PR valid and healthy child with a positive value of the loan and add credits to the credit balance in accordance with the amount of data selected for retrieval from the queue.

In accordance with another aspect of the present invention, is provided a method of allocating credits child elements in the data network. Each credit can be used for data transmission. Loans are provided at least one valid, healthy child and the child element with negative credit meter. Supported credit balance representing a total volume of Unallocated credits and loans shall be deducted from the credit balance.

In accordance with another aspect of the present invention, is provided a method of scheduling data transmission in a data network. The data network includes many child elements. Create multiple queues management of data. Each queue control data transfer can contain at least one identifier corresponding to a valid child element and has a priority level, which is determined in accordance with the requirements of the loan management. Each valid child element is associated with one of multiple queues management of data. Each valid child element has the status of a loan that meets the requirement to counter the credit is for the associated queue control data transmission. At least one valid child element is selected for retrieval from the queue according to the priority level of the queue transmission control data corresponding to the aforementioned valid child element. To the credit balance is added to the credits corresponding to the amount of data retrieved from the queue. Each valid and workable child element is present in one of the queues management of data.

BRIEF DESCRIPTION of DRAWINGS

A more complete understanding of the present invention, its advantages and properties that can be achieved with the use of the following detailed description, considered together with the attached drawings, where:

Figure 1 shows a block diagram of an example process for scheduling data transmission in accordance with traditional technology;

Figure 2 shows a block diagram of an example process planning data-based fair Queuing using the weighting coefficients and inverse control loans;

Figure 3 shows a block diagram of an example process planning data-based fair Queuing using the weighting coefficients and the reverse loan management, constructed in accordance with the principles of the present invention;

Figure 4 shows b is OK diagram of an exemplary dispenser loans designed in accordance with the principles of the present invention;

Figure 5 shows a functional diagram of an example process works distributor of loans in accordance with the principles of the present invention;

Figure 6 shows a functional diagram of an example process of lending in response to changes in the admissibility of child elements in accordance with the principles of the present invention;

7 shows a block diagram of an exemplary one-dimensional cyclic planning process using the weighting coefficients and rotation for child elements with large weights in accordance with traditional technology;

On FIG shows a block diagram of an exemplary two-dimensional cyclic planning process using the weighting coefficients and rotation for child elements with large weights, constructed in accordance with the principles of the present invention;

Figure 9 shows a block diagram of an exemplary two-dimensional cyclic planning process using the weighting coefficients and rotation, there are four levels of priorities, constructed in accordance with the principles of the present invention;

Figure 10 shows the block diagram of the exemplary base selector transmission constructed in accordance with the principles of the present invention;

N is 11 shows a block diagram of an exemplary advanced selector transmission, designed in accordance with the principles of the present invention;

On FIG shows a functional diagram of an example process of selecting children at fair Queuing using the weighting coefficients in accordance with the principles of the present invention; and

On FIG shows a functional diagram of an example process of selecting, in response to the increase of credit and changes to the admissibility of child elements in accordance with the principles of the present invention.

DETAILED description of the INVENTION

Before to describe exemplary embodiments of corresponding to the present invention, note that embodiments of consist primarily in a combination of hardware components and processing steps related to implementing a system and method for fair Queuing in traffic is managed on the basis of frames, which include restrictions exchange rate and the guaranteed rate of exchange for the children competing in the scheduler fair Queuing using the weighting coefficients. Accordingly, components of the system and method where it is reasonably represented in the drawings, the adopted notation, this shows only those details that are critical on what I understand of embodiments of the present invention, in order not to clutter the description of the details that are so clear to those of ordinary skill in the field to which the invention relates.

Such related terms as "first" and "second", "lower" and "upper"and the like, may be used here solely to distinguish one entity or element from another entity or element, not demanding and not implying a mandatory between such entities or elements of the physical or logical relations or order. The "root" node indicates the highest level node in the tree," fair Queuing or the highest level node in the hierarchical "tree" fair Queuing. "Heir" of a particular node is any node below and associated with that particular node. Similarly, the "ancestor" of a particular node is any node above and associated with this particular site.. the Terms "child, "child node" or "child elements" refers to any direct successors of a node in the tree planning. In General, when discussing relations with a particular node, the term "subsidiary element" refers to a node (host or queue scheduler), located one level below the considered node. In addition, any node which is naslednikava higher level may be called "child node" or "child".

One of the embodiments of the present invention provides a system, method and apparatus for fair Queuing with callback management credits that can be used in the presence of traffic with adjustable baud rate. The system and method include restrictions exchange rate and the guaranteed rate of exchange for the child elements child elements, competing in the scheduler fair Queuing using the weighting coefficients. The mechanism of the credit balance ensures the preservation of loans in case, when children return unused credits. Prior to that unused credits were provided by the distribution system loans with no information about how long this child could remain within its limits the rate of exchange and continue to have a lot of data to send.

In addition, unlike traditional technologies, embodiments of the present invention allow children to change their condition of admissibility, thereby providing for easy incorporation of child elements with speed limits of currency.

Figure 3 shows the estimated fair scheduler Queuing 28 with the improved feedback management loans ("WFQ-ICM-Plus"), designed in accordance with the principles of the present invention, which includes a transmission selector 30, the dispenser 32 credits and a database of credit state child elements 34. The transmission selector 30 selects a child element among the valid child elements for data transmission. A separate process for determining the admissibility 36 decides whether to select a child element data. Detailed description of the functioning of the process of determining the admissibility 36 is outside the scope of the present invention; it is only then that the process of determining the admissibility 36 decides which child elements are allowed to choose. In its simplest form the process of determining the validity represents the data present in the child element. In a more complex form of available data may contain restrictions exchange rate at different levels of the hierarchy. This leads to differences in behavior from traditional technology, which is that child elements with negative credits can be selected for transmission by the transmission selector 30. In addition, in embodiments of the invention, it becomes possible to "disable" the previously valid child element of another process that is also impossible under traditional technology.

Dispenser 2 credits includes credit balance ("SV") 38, which contains all of the excess credits for the system. The dispenser 32 credits is a process of equitable distribution using weights, which provides loans from the credit balance 38 all valid child element and all child elements that have negative credit. The dispenser 32 credits in each moment keeps track of the amount of loans issued to each child item in the database of the credit status of the child elements 34.

Unlike previous WFQ schedulers, ICM, embodiments of the present invention have the advantage that they do not require the system to know exactly how much available data. Instead, the dispenser 32 credits must know that the child is "valid". The dispenser 32 credits may distribute credits to any valid child element. Thus, together with the variants of implementation of the present invention are able to operate freely, interacting processes, for example, the shaper signal baud rate (rate shaper). Theoretically, a child may receive a much larger volume of loans than the amount of data, which currently has a child element, or will be able to deliver in the near future. However, if the child is PE is ahadith from "valid" to "invalid", all loans that this child has acquired, withdrawn and returned to the credit balance 38.

The transmission selector 30 selects the valid child elements for data transmission. In General, the choice of child elements prefers child elements with large values of the counters loans. Thus, it is more likely that transmission will be selected child element with a high positive count loan than a child element, having a small positive or even a negative counter value of the loan. When the child passes the data, credits are deducted from its current amount of credit database of the credit status of the child elements 34 and returned to the credit balance 38 for redistribution to other valid child elements and child elements that have a negative balance.

Existing schedulers WFQ-ICM does not allow for the transfer of children with a negative count of loan except when it is necessary to complete the transmission of a frame is initiated with a positive counter loan. However, the conventional technology does not allow disable or do not valid for the transfer of child elements after obtaining the loans, it does not need this feature.

Figure 4 shows a simplified implementation of an exemplary dispenser 32 credits. In the eat case of cyclic dispenser credits 40 distributes the credits allowable and having negative credit child elements with the same speed, which of the scheduler 28 out data. In other words, the possibility of transmission from the transmission selector 30 initiate distribution of credit to the distributor 32 credits.

During the cycle of distribution of credits each valid child element and child element with negative credit to get some inputs in a loop in accordance with their weights. Each child element in the cycle receives one credit when it reaches the beginning of the circular ("RR") queue distribution 42. In other words, one cycle RR gives each child one "credit". Thus, during a full cycle lending to each child element "i" (referred to child_iavailable w_iloans, where w_i" represents the value of the weighting factor for child_i. The number of cycles RR, necessary for the distribution of W; credits each child element_iis w_i. The lending cycle is completed when each child element child_igets w_iloans. Thus, the duration of the lending cycle is specified child element with the highest w_i. When the child receives the full value of their weight in this cycle, it will be temporarily stored in the queue exceeds the weights 44 to expectations, and e which have not distributed the loans until the next cycle of credit.

In the prior WFQ schedulers-ICM distribution of loans takes place exactly at the same speed as the transmission, so never balance credit balance 38. Available for distribution to those loans that are returned from the selector transmission 30.

In contrast, embodiments of the present invention allow the dispenser 32 credits to support in case of need a positive credit balance 32. Credit balance 32 can become very large due to the fact that the previously valid child elements, with positive loans, become invalid. To compensate for this potentially large credit balance credit balance, the dispenser 32 credits is not required to give the same number of credit bytes coming from the transmission selector 30 (indicated as "N")as bytes, provided the child elements (labeled "M"). Thus, when the credit balance 38 contains excessive loans (i.e., SV>0), allocator credits 32 accelerates the distribution of credit by simply increasing the number of credits granted for one full cycle of the queue distribution RR 42, so that M>N. in Other words, during the cycle RR dispenser credits 32 distributes the M bytes of the loan each child in turn. All excess credits can is transferred to the next cycle RR. On the other hand, if the credit balance 38 when the magnification M is set to zero, the frequency distribution (F) can be increased so that M*F=N, thereby still providing the M bytes of the loan each child until it reaches the end of the cycle RR. The increase in the number of loans provided during the entire cycle RR provides for the maintenance of justice among child elements. It should be noted a few exceptions in the distribution of the increased amount of M bytes loan: child elements that would exceed their weight after giving M bytes of the loan, only get the remainder of their weight, and the child elements that are not valid for transfer, but collect the loan to bring it back to zero, never given more credit than is necessary to return to a zero value of the loan. Other embodiments of the dispenser credit - based queue management, vector or other means - can also speed up the distribution of credit by increasing the "normal" speed distribution of loans are fundamentally similar to those described here.

Figure 5 shows an exemplary functional diagram that describes steps performed by the distributor 32 credits in response to the ability to allocate credit. Figure 5 distribution is the amplifier 32 credits included the transmission selector 30 once per N bytes of transferred data (step S100), however, in another embodiment, may be a periodic trigger that solves the same task. It is important to note that in alternative embodiments, the implementation of the present invention, the dispenser 32 credits may have real information on the total number of bytes transferred so that loans could be distributed to groups or sections of N bytes. It should also be noted that the following process still does not take into account changes of admissibility, however, questions of admissibility are taken into account below, see FIGURE 5.

If the dispenser 32 credits is not at the beginning of the cycle RR (step S102), that is, loans have already been distributed to some children in the current queue RR, the process selects a child element child_iin the beginning of the current queue RR in order to distribute his credits (step S104). In this case, use the previous state the quantity of credit granted M. However, if the dispenser 32 credits is ready to begin a new cycle RR (step S102), that is, the previous RR cycle was completed, the dispenser 32 credits decides whether to continue the cycle distribution of loans, or to start a completely new lending cycle (step S106). If this is the beginning of the lending cycle, planning selects all RR (step S108). So far has considered only PR is the process of planning, supporting only one turn RR, so step S108 only resets the planning parameters and starts the process all child elements to the queue RR. However, in accordance with the following description for FIG, a sample implementation of the present invention supports multiple queues RR, reflecting the different priorities of child elements, in this case, the step S108 could choose to handle another queue RR. If this is not the beginning of the lending cycle, then a new queue RR is not required.

Returning to decision block S106, if the lending cycle is just beginning, the dispenser credits 32 determines whether there is excess credit balance (step S110), in this case - more credits than can produce one event transmission (N). If there is excess credit balance, the dispenser 32 credits included in the cycle of accelerated distribution of credits (step S112 (), where the distribution of loans (M) during this event, the allocation of credits and the remaining events distribution of loans in the current cycle RR exceeds loans transferred between events distribution of loans (N), i.e., M>N. otherwise, if the remaining credit balance is missing (step S114), the volume of credits that must be distributed during this event, the distribution of loans and mortgage the e remainder of the cycle RR, is set equal to the loan volume is usually transmitted between events distribution of loans, that is, M=N (step S114). Note that other embodiments of the present invention may use different thresholds for N in block decision S110, for example, SV>x bytes, where x is a static or dynamic number that is used to introduce hysteresis in the decision to accelerate the allocation of credits.

Distribution of loans begins with choosing the child child_iin the beginning of the current queue RR (step S104). If the credit balance is greater than or equal to the number of credits that must be provided to each child for the current cycle RR (step S116), that is, SV>=M child child_iis the least of its residual weight in the cycle of lending and the number of credits that must be provided for the RR cycle (step S118), M the Volume of loans granted to the child child_iis deducted from the credit balance (step S120), and the RR cycle moves to the next child in line RR (step S122).

Returning to decision block S116, if the credit balance exceeds the residual weight for the child child_i(step S124), then the child element child_iis it residual credit weight (step S126). The volume of loans give is the R child element child _iis deducted from the credit balance (step S120), and the RR cycle moves to the next child in line RR (step S122). However, if the residual weight for the child child_iexceeds the credit balance (step S124), the credits are not allocated, and the current event to the allocation of credits completed, the child element child_istill early in the RR queue waiting for the next event of the allocation of credits.

Figure 6 shows exemplary functional diagram that describes steps performed by the distributor 32 credits in response to changes in state child element. The dispenser credits 32 detects a change in the state child element child_i(step S128). Changes of state can be declared as a separate process (inside or outside of the scheduler), for example, by setting or clearing a flag corresponding to child transmission of events or messages. If the child element child_imoved from the invalid state to the valid (step S130, the branch "YES"), the child element child_iis already in the credit system (step S132, the branch "YES"), the distributor 32 credits just clears the flag delete pending for the child child_i(the stage is set s134). As described below in connection with step S150, this flag expectations which the pressure was set to request removal of the child from the dispenser 32 credits, when he returns to normal. Child element child_iretains the ability to get loans depending on their weight and ordinal place in the queue RR. However, if the child element child_iat the moment, is out of the credit system (step S132, the branch "NO"), and he has not yet received loans exceeding its weight weight_iin the cycle of credit (step S136, the branch "NO"), the child element child_iis placed at the end of the queue RR (step S138) and will receive credits in the current cycle of lending. If the child element child_ialready exceeded its weight weight_iin the current cycle of lending (step S136, branch "YES"), the child element child_iis placed at the end of the queue is exceeded weights (step S140) and will not receive credit again before the next cycle of credit.

Returning to decision block S130, if the transition child element is again a valid child element, then the child goes into a state of inadmissibility. If the newly invalid child element child_iat the moment possesses a positive credit or does not have the credits (step S142), i.e. credits_i>=0, all excess credits will be refunded to the credit balance (step S144), and the counter credit for child child_iset to zero (step S146). ZAT is m child element child _iremoved from the credit system (step S148). It should be noted that the destruction of the credit system, the easiest way is achieved, if you wait for the promotion of the child in the front of the queue RR and remove this child instead of giving him credit. This method is one of the potential uses of the deletion flag. However, in other embodiments, implementation of the newly invalid child element child_ican be removed from the system immediately after the return of its loans in the loan balance.

Returning to decision block S142; again if invalid child element has negative credit, i.e. credits_i<0, simply set the deletion flag, and it is ready for removal. However, it should be noted that all newly invalid child elements with a negative credit balance is not removed from the credit system, while replenishing your deficit of credit loan balance, that is, a child element child_inot deleted until you reach the credits_i=0.

Figure 7 block diagram of an exemplary one-dimensional cyclic planning process 46 ("WIRR") using the weighting coefficients and rotation for child elements with large weights in accordance with conventional technology. The planning process WIRR 46 uses two queues: cyclizes the Yu ("RR") turn 48 and turn excess weight 50. All of the children who should receive loans in the cycle of lending, beginning in the RR queue 48. Initial conditions are shown in FIG.7, where the RR queue contains four child elements (for example, a, b, C and D), where a has a weight of 10, has a weight of 4, and C and D have weight 2. Since the number of cycles RR in one cycle of lending is dictated by the child element with the largest weight, and the child element And has a weight of 10, one cycle of lending can include up to ten cycles RR.

During the first cycle RR credit is D, the child item at the top of the queue RR 48, and then D is moved to the end of the queue RR 48. Similarly, the loan is issued With, and As, with each of the child elements is moved to the end of the queue RR 48, thus, D is returned to the beginning of the queue. During the cycle RR 2 credit given D, the amount of loans distributed for D in this cycle lending, greater than or equal to its weight, i.e. credit_D>=current RR. Thus, D is moved to turn excess weight 50 to the end of the lending cycle. Similarly, the credit is given, which is then moved to the end of the queue is exceeded, the weight 50. Finally, the loan is issued and who then moved to the end of the queue RR 48. During cycle 3 one credit is issued, and one credit is issued A. during cycle 4 of the Institute of credit shall be issued, and one credit is issued; however, getting your weight in the form of loans for the lending cycle, the child element is moved to the end of the queue exceeding a weight of 50, leaving in line RR only And 48. During the remaining cycles RR, for example, 5-10 cycles, the child item And receive one credit for the cycle.

Effective sequence distribution of loans for this one-dimensional WIRR looks like this:

DCBA, DCBA, VA, VA, a, a, a, a, a, A.

Thus, during one segment of the sequence distribution of loans package is consistent distributions to the child A. This sequence represents a potential threat to the stability of the system, if the child element And the end data, whereas accumulate credits he can be very fast.

Variant implementation of the present invention improves the planning process WIRR, introducing a new two-dimensional WIRR scheduler so that the scheduler could evenly distribute the credits child elements with large weights. On FIG shows a block diagram of an exemplary two-dimensional WIRR scheduler 52, constructed in accordance with the principles of the present invention. Two-dimensional WIRR scheduler 52 implements instead of one of the RR queue of the multiple queues RR representing the bandwidth or category weights. First measurement planning the training is within the category of bandwidth where cycles lending WIRR ensure justice between children within the same category bandwidth. The second dimension of planning between categories throughput, where a balanced alternation between queues RR maintenance scheduler first dimension implements the multiplier bandwidth associated with the categories of bandwidth.

Two-dimensional WIRR scheduler 52 may include at least two sets of RR queues that are associated with all the excess weight, where each queue "i" is configured as a category bandwidth in the form of a multiplier bandwidth "n_i". Child elements are interleaved in the queue RR based on the normalized weights (later) in a loop WIRR and between RR queues in order of service queues between full cycles WIRR. In the scheduler of the second dimension of all RR_iwith a multiplier of n_iruns n_itimes as many full cycles WIRR as a queue when 1 (denoted by x1). For example, in a two-dimensional WIRR scheduler 52 (FIG) is a high-priority (HP) of all RR 54, having a multiplier 4, a high-priority queue excess weight 56, a low-priority (LP) queue RR 58, with a multiplier of 1, and a low-priority queue excess weight 60. The lending cycle WIRR vysokopiaristye the Noah queue 54 is performed 4 times for each execution cycle lending WIRR low-priority queue.

Fixed template for working with queues RR is acceptable if it is possible to save labor costs, which means that useful planning decisions can be taken even if some of the queues RR does not contain a valid child elements. For example, for two-dimensional WIRR scheduler 52, with HP all 54 with a multiplier of x4 and LP queue 58 with a multiplier of x1, the pattern of distribution of credits looks like: HP, HP, HP, HP, LP, repeat. The weights used for the lending cycle WIRR, scaled by the multiplier of the second dimension, where the normalized weight equal to the full weight divided by n_i.

For example, using the same scales and the child elements that were used above in connection with FIG.7, in a two-dimensional WIRR scheduler 52 (FIG) child elements are placed in such a way that a and b are in the HP queue 54, and C and D are in the LP queue 58. Child element And has a normalized weight of 2.5, and the total weight is equal to 10 (i.e., standards. weight * factor = total weight; a 2.5*4=10). Similarly, is the normalized weight of 1 and the total weight is 4 (i.e., 1*4=4). Because the multiplier for LP queue 58 is equal to 1, C and D retain their original weight equal to 2.

During the first cycle of lending WIRR two-dimensional WIRR served only HP queue 54. Thus, the dispenser loans during the cycle WIRR 1 provides one redit, A - two credits, while retaining the residual weight of 0.5 child element of A. for lending cycle WIRR 2 again served only HP queue 54, but this time gets 1 credit, And receives 3 credits (i.e., 2.5 weight for this cycle + 0.5 residue weight = 3 credits). The third cycle WIRR is a repetition of the cycle WIRR 1, where 1 receives the loan And receives 2 credit with a balance of 0.5. The fourth cycle WIRR is a repetition of the cycle 2, where b gets 1 credit, And receive 3 credits. The fifth and last cycle WIRR servicing LP queue 58, with child elements C and D receive 2 credits. Thus, an effective procedure for granting loans for the full cycle lending for two-dimensional WIRR scheduler 52 looks like this:

.

It should be noted that the greatest package consecutive distributions reduced to three distributions And that less than half the greatest service one-dimensional WIRR 46, corresponding to the conventional technology. It should also be noted that this procedure can be implemented using a single queue of excess weight because you have only one queue RR.

The algorithm is not O(1), that is, the hierarchical scheduler with computational complexity than O(1) and use the known notation big-O, may be satisfactory for the second dimension because scalability is not required. As shown above, a strong alternating limits the length of the packet from the child elements with the highest weights. Despite the fact that the above review was conducted in the context of the dispenser loans, it is envisaged that a two-dimensional WIRR scheduler 52 of the present invention can be used as a planning process retrieval queue transmission selector transmission 30.

The concept of two-dimensional WIRR can be extended to implement systems with more than two priority levels. Figure 9 shows the block diagram of WIRR scheduler 62, with four levels of priority, presents four priority queues RR: high priority (HP) turn 64, sredneprogredientnaya (Mr) turn 66, low-priority (LP) queue 68 and foremost a very low priority (the VLP) 70. Selected fixed multipliers between queues to provide a large dynamic range planning. For example, suppose that the largest normalized value of the weight for all children in all queues RR is equal to 8, the smallest normalized weight equal to 1, the maximum total weight for all of the child elements is 4096 (8⁴). The selection is made on the basis of weight, so when all queues contain child elements, every 585 event planning HP queue 64 512 is selected times, Mr obvious is go 66 64 is selected times, LP queue 68 is selected 8 times, a VL queue 70 is selected once. WIRR scheduler 62 saves labour costs, so the queue does not contain child elements that are not selected. Designed or configured template allocation of credits should be to maximize distribution opportunities queue scheduling with large weights. In addition, every time the queue should be full standard cycle WIRR. Weight queues, shown in FIG.9, are illustrative, but do not represent the only strategy "weight" of queues RR. For example, another strategy using weights could provide a uniform change in the weights of the queues instead shows an exponential strategy. Another strategy could implement dynamic weight queues (multipliers), which vary depending on the weights of the child elements that are active in the system.

The dispenser credits 32 responds to a non-zero credit balance by increasing the speed of distribution of credits, in other words, the accelerated distribution of loans (CDA), which is denoted as M>N in figure 5. The way CDA combines several cycles RR in one cycle of lending in one pass processing along the line RR. This is accomplished within the lending cycle of any category one bandwidth, therefore the second signal is in the planning explicitly not included. This method requires knowledge of the beginning and end of the RR cycle and assesses the value of a CDA, or M, at the beginning of each cycle RR. The number of cycles RR, combined cycle CDA, usually 2 (M=2). It seems also that M should be increased to 4, when the credit balance 38 is relatively large, for possible configuration as a threshold for comparison with the credit balance 38.

Another option exercise combines the maximum number of cycles RR in one pass by allocating all residual weight of each child element in the current cycle of lending, thereby lending cycle WIRR ends. Another implementation counts the number of child elements that are involved in the cycle RR, and sets the acceleration factor 1+SV / "the number of child elements, effectively eliminating credit balance 38 in one pass on the current RR queue.

The way CDA allows you to return the speed distribution of loans in the norm by the middle of the accelerated cycle RR by passing opportunities, the allocation of credits. In other words, if M is 2, and the credit balance 38 returned to a zero value, the loans are distributed only all other ways, for example, M×N×0,5=N. Check continuous acceleration just until the credit balance is greater than the minimum of M and the residual weight weight_ichild element child_iat the beginning of the ocher is di RR can use the credits.

Cycle RR at any level of priority may be accelerated distribution of loans (CDA). CDA is included in the beginning of the cycle RR. In the beginning of the cycle RR selects the acceleration factor M, which is valid for the entire cycle RR. The assignment of the child elements of the normalized weights less than or equal to 1 should be prevented, because the acceleration of this type can participate only child elements with the normalized weight factor >1. Child elements whose residual weight in the cycle of lending to less credit, which imposes CDA, receive only its residual weight (that is, the possibility of accelerating lost fully or partially).

Now let's move from the distributor credits 32 to the selector of the transmission 30, constructed in accordance with the principles of the present invention. Existing planners with feedback control credits (ICM) contained only one transmission queue that serves only children with positive loans. Child elements were chosen for transmission, for example, in accordance with a cyclic order and was placed at the end of the transmission queue. Then, for transmission was selected child, who was in the front of the queue.

Figure 10 shows an exemplary basic structure of the transmission control 72, constructed in the accordance with the principles of the present invention. In accordance with one embodiments of the present invention, the basic structure of the transmission control 72 includes three separate queue management data transfer: all positive credits 74, turn negative credits 76 and the extreme negative credits 78. All child elements that are valid for the transfer, for example, work and possess the data present in one of the queues transmission control data. The priority selector 80 selects the queue management of data, from which you want to transfer, based on a given system of priorities. In other words, the transmission control data with the highest priority that contains the child element is always selected first queue of the transmission control data having a lower priority. In each of the queues management of data child elements are selected simply cyclically, that is, without weights. Possibility of transfer creates a corresponding possibility distribution of loans.

Child elements are sorted in the queue control data transfer based on the number of credits they have. Child elements dynamically moved between queues management of data as it changes their the loan balance. Child elements with a positive counter value of the loan, queued positive credits 74. If not, the function "reset credit in the system in the case when the child becomes invalid, the expected behavior would be the following: transmit data only child elements from the queue positive credits 74. Because the present invention permits the discharge of the loan when the loan balance is greater than N), the sum of all loans held by all active children, can be negative. Child elements with a negative counter value of the loan queue negative credits 76.

Standard turn positive credit transfer 74 and turn negative credits 76 contain child elements with normal values of counters loans. Child elements in the queue positive credit transfer 74 has gotten a little more credit than made gear, while in line negative credit transfer 76 got a little less credit than made gear. Transfer from the standard queues with positive credit transfer 74 represents a normal operation mode if the prohibition does not cause fluctuations in the credit balance 38. However, many children will be detained in the queue negative is reditab transmission 76 after the transfer until until the counter credit child will not be restored distributor 32 credits.

It can be assumed that the amount of credits possessed by the currently active child elements, can be negative, thus, some child elements having a negative counter value of the loan, you can randomly get right to transfer, further reducing the value of its counter loan. However, the child elements with a large number of gears negative values can be separated to reduce the "injustice". Thus, the set threshold value, for example, negative values of the maximum size of transmission media, with child elements that have a negative credit balance below this threshold are placed in the queue extreme negative credits 78. Transfer from the queue extreme negative credits 78 assumes the presence of a very large excess of the credit balance 38 in the dispenser 32 credits, which may require special attention. All extreme negative credits 78 prevents "rolling" child elements to very low loan balance, unless all of the children involved in this "rolling". Transfer from the queue extreme negative is reditab 78 indicates a problem with the credit balance 38, which causes system instability. Emergency measure that can be taken to protect the credit balance of 38 from additional growth is the reduction in the rate of spending of the credit transfer (for example, waste transfer N/4 instead of N credits). This imbalance value data introduces an error in the algorithm fair Queuing using weights as to transfer some of the data will be spent N, and other - N/4, but this is a simple implementation of protection from the endless growth of the credit balance 38.

Additional embodiments of using a more advanced structure transmission control 82, as shown 11. This improved structure transmission control 82 combines three queue management of data, discussed above, with the additional queues (optional) can be used to increase the flexibility of planning and adding new properties. For example, the structure of the transmission control 82 may combine child elements with the given priority, for example, the child elements that contain packets of voice data, with child elements of a fair Queuing through the queue control bypass highest priority 84. Improved management structure lane is giving 82 and the above methodology allows to combine planning with the priorities and fair Queuing with minimal cost.

Optional queue control data transfer can also include all extreme positive 86 credits and all unknown child elements 88. All extreme positive credits 86 prevents jumps counter credit caused by the stop of the transmission system, thereby increasing the resistance of the credit balance. Despite the fact that all extreme positive credits 86 is not mandatory, its use is desirable, because the child elements with large weights in the absence of priority transmission can quickly build up credits. Large stocks of loans are dangerous for the stability of the system, as in the case, if the child becomes invalid, loans suddenly returned to the credit balance 38. If a child element has a large counter value of the loan, the transmission selector 30 should interview the child to determine whether there is no danger of achieving this child of the upper threshold of the loan. The upper threshold of the loan can be set by the system designer in accordance with the characteristics of the transmission media, including parameters such as current traffic. If the child violates the upper threshold of the loan, this child element must be moved in ocher the ü extreme positive credits 86, to receive priority service. All unknown child elements 88 allows for the possibility that a child known to the parent scheduler, which is not yet known current scheduler. If the current scheduler is selected for scheduling and has no other valid child elements, then the required child element provides all unknown child elements 88.

On FIG shows an exemplary functional diagram that describes steps performed by the transmission selector 30 when selecting child elements of a fair Queuing. The transmission selector 30 determines if the child is a new selection (step S152). If not, the transmission selector 30 continues to transmit the frame from the queue and(or) from the child element matching (matching) with the previous selection (step S154). If the choice is new (step S152), the transmission selector 30 selects the transmission queue with the highest priority that contains child elements for retrieval (step S156), and selects the child_iat the beginning of the transmission queue for transmission (step S158). After you select a child element for transmitting the transmission selector 30 subtracts the number of bytes transferred ("N") of the amount of available credit (credit_ifor this child element child_i(step S160). When the gear selector is 30 reaches the end of transmission (step S162), if child_iis no longer valid (step S164), child_iis removed from the transmission system (step S166), i.e., child_ino longer is visible to the selector of the transmission 30. However, if child_iremains valid (step S164), child_iagain placed in the transmission queue, which is suitable for the remaining number of credits child credits_i(step S168).

On FIG shows an exemplary functional diagram that describes steps performed by the transmission selector 30 in response to the increase in loans and changes admissibility. The transmission selector 30 determines whether child_inew child element (step S170), which means its absence in the queue system selector transmission. If child_iis not new, and the transmission selector 30 determines that the child_iis no longer valid (step S172), if child_icurrently not transmitting data (step S174), child_iis removed from the transmission system (step S176). Otherwise, if child_icurrently transmits data (step S174), the transmission selector 30 does not respond. This reaction occurs within the extraction process from the queue, FIG.

Returning again to decision block S172, if child_iis valid, a credits_ispecifies that the child has received enough new credit is to change the levels of priority (step S178), because child_icurrently not transmitting (step S180), the child_iis removed from the current transmission queue (step S182) and is placed at the end of the transmission queue, indicated by the number of credits_i(step S184), i.e., the transmission queue with a higher priority.

In addition, refer again to decision block S170, if child_irepresents a new child element, selector transmission 30 just puts child_iat the end of the transmission queue, indicated by the number of credits_i(steps S184).

The present invention can be implemented in hardware, software or combination of hardware and software. To perform the functions described here is suitable computing system of any type or other apparatus adapted for the implementation described here.

The usual combination of hardware and software may be a computer system, specialized or General purpose, having one or more processing elements, and a computer program stored on the drive, which, when loaded and executed, controls the computer system such that one carries out the methods described here. The present invention can also be embedded in a computer program product, which contains all of the properties that provide the state of the implementation described here, and which, when loaded into a computer system capable of implementing these methods. The drive is any volatile or non-volatile storage device.

A computer program or application in the present context means any expression, in any language, in any code or in any notation, of a set of instructions intended to induce a system capable of processing information to perform some function either directly or after at least one of the following operations: a) conversion to another language, code or other notation; b) reproduction in a different material form.

In addition, if not reversed, it should be noted that all of the accompanying drawings is not to scale. It is important that this invention may be embodied in other forms without departure from its spirit and essential attributes, and therefore, when specifying the scope of the invention to apply should, primarily, to the following claims rather than to the preceding description.

1. System for planning, selecting data for transmission in a data network, where the data network has many child elements, including:
the dispenser loans, provides:
the provision of loans at least one is from a valid child elements and child elements with a negative count of credit, each credit can be used to transfer a certain amount of data.
support justice between the child elements in the ratio of loans;
maintaining a credit balance representing a total volume of Unallocated credits; and
subtraction of the loans from the credit balance; and
the selector transmission, communication associated with the dispenser loans, the transmission selector operating to:
select at least one valid and workable child element to retrieve from the queue;
select at least one valid and workable child element in the choice of a valid and healthy child with a positive value of the loan and
add credits to the credit balance corresponding to the amount of data selected for retrieval from the queue and update tool validity, determining the condition of admissibility for each child element, where the condition of validity indicates whether a valid child element data on the basis of criteria other than fair Queuing using the weighting factors, which influence the dispenser loans, including, hence, is her least one of the following: the speed limit sharing, limiting surge and data availability.

2. The system according to claim 1, where the dispenser loans are able to additionally perform the following operations:
the removal of all credits previously allowed and healthy child until the child element will not become inoperative or invalid; and
add shot of credits to the credit balance for re-distribution.

3. The system according to claim 1, where the dispenser loans has at least one circular queue management, containing at least one identifier of at least one of the following:
valid child element and a child element with a negative count of credit, where the dispenser loans additionally performs the following functions:
the alternation of loans child elements within the first circular queue management;
providing one credit for each child element of the first cyclic queue in a loop;
the repetition of cycles until each child will not get the amount of credits corresponding to the weight of the child;
remove each child from the first circular queue management when a child element is the amount of credits corresponding to the weight mentioned the daughter is his element; and
in response to providing each child the amount of credits corresponding to the weight of the referred child, return the child in the first circular queue management.

4. The system according to claim 3, where the dispenser loans - scheduler of the second dimension using the weighting coefficients and the rotation supporting multiple circular queue management, each circular queue control contains at least one identifier of at least one of the following: a valid child element and a child element with a negative count of credit, each circular queue management is at least one of the following: category bandwidth and the category weight, and each circular queue management receives a multiplier, where the dispenser loans additionally performs the following functions;
the alternation of choice cyclic queue management for the allocation of credits, where each circular queue control selects the number of times its corresponding multiplier alternating selection of circular queue management for the allocation of credits, each circular queue control selects the number of times its corresponding multiplier;
the choice of the first circular queue management is La distribution of loans;
credits child elements in the first circular queue management, where each child is provided the volume of credits that corresponds to the weight assigned to the referred child element for each cycle of the cyclic queue management, and where the loans are child elements in a cyclical manner;
the choice of circular queue management in an alternating until all cycles are eliminated; and
loans to affiliated items found in the selected cyclic queue management queue.

5. The system according to claim 1, where the dispenser loans additionally performs the following functions;
maintains a balance between the lending and the transmission of data;
provides loans of approximately with the same speed as normal data transmission; and
responds to the presence of the remainder of the loan balance, increasing the rate of lending.

6. The system according to claim 5, where the credit balance is redundant before the start of the cycle, the dispenser loans, in addition, works to increase the speed of the credits allowable child elements by combining cycles one through the provision of multiple loans each child in a single pass; and where redundancy includes one of the SL is blowing: the excess of a predetermined threshold, the excess of the loan volume that is greater than the amount of the loan absorbed by a single transfer event, and the larger of zero.

7. The system according to claim 1, where the transmission selector has multiple queues management of data to retrieve from the queue, where each queue transmission control data includes at least one identifier valid child element child element having the priority level specified in accordance with the requirements of the counter of the loan, and the transmission selector is configured to assign each valid child element from the queue management of data, each valid child element has a credit status, the relevant requirements to the counter of the loan assigned to the queue element management data transfer.

8. The system according to claim 7, where the queue transmission control data include all positive credit transfer, all negative credit transfer and the extreme negative credit transfer and where:
the first threshold counter credit between all positive credit transfer and turn negative credit transfer is equal to zero;
the second threshold counter credit between all negative credit transfer and foremost extreme negative credit transfer Rawa is the negative value of the maximum transmission unit to the data network;
all positive credit transfer has a higher priority in selecting than all negative credit transfer; and all negative credit transfer has a higher priority in selecting than all extreme negative credit transfer.

9. The system of claim 8, where the queue management of data additionally include at least one of the following:
all extreme positive credit transfer, crawl queue and the queue unknown child elements:
crawl queue has the highest priority level and when transferring from the queue traversal loans in the loan balance will not be returned;
all extreme positive credit transfer has a higher priority than the queue positive credit transfer, all negative credit transfer and the extreme negative credit transfer; and all unknown child elements containing valid and workable child element with unknown credit status and having the lowest priority level.

10. The system of claim 8, where the transmission selector is additionally capable of reducing the credits allocated to the transmission of data from the queue extreme negative credits by adding credits to the credit balance in accordance with the portion of the volume data, selected for retrieval from the queue.

11. The allocation of credits child elements in a data network, where each credit can be used to transfer a certain amount of data, including:
the definition of the state for each child element, where each child element can transmit the data based at least on limiting exchange rate;
loans, at least, acceptable and healthy children and children with a negative count of credit;
support credit balance representing the total available amount of Unallocated credits; and
subtraction of the loans from the credit balance.

12. The method according to claim 11, further including:
the removal of all credits previously allowed and healthy child
element until the child element will not become inoperative or invalid; and
add shot of credits to the credit balance for re-distribution.

13. The method according to claim 11, further including:
realization of two-dimensional cyclic scheduler using the weighting coefficients, rotation and having multiple circular queue management, each circular queue control contains at least one Eden is idicator valid child element or a child element, with a negative count of credit, each circular queue management is at least one of the following: category bandwidth and the category weight, and each circular queue management receives a multiplier;
the alternation of choice cyclic queue management for the allocation of credits, each circular queue control selects the number of times its corresponding multiplier;
the choice of the first circular queue management for distribution of loans;
credits child elements found in the first circular queue management;
the choice of circular queue management with residual weight factor in a loop until all cycles are eliminated; and the provision of credit child elements found in the remaining cyclic queue management queue.

14. The method according to item 13, where the loans are child elements,
indicated in the selected circular queue in accordance with the normalized weighting factors for each child; and
where the sum of weights for each child element of all cycles is equal to its normalized weight, multiplied by the multiplier for circular queue.

15. The method according to claim 11, where, if the credit balance is greater than the amount of data selected for extraction socured between events distribution of loans additionally includes:
implementation of one or more cyclic queue control that contains one or more child elements for use in alternating lending between acceptable and healthy children or children with a negative credit balance; and
additional loans child elements in a circular queue management by combining several cycles in one by providing multiple loans each child for a full pass through the circular queue management.

16. The planning method of selecting data for transmission in a data network, where the network data contains multiple child elements, including:
the definition of the state for each child element, where each child element can transmit the data based at least on the speed limit of the surge;
creating multiple queues management of data to retrieve from the queue, where each queue control data transfer can contain at least one identifier corresponding to a valid child element having the priority level in accordance with the requirement of the counter value of the loan;
assign each let the WMD child one of the many queues transmission control data, each valid child element has the status of a loan that meets the requirement to count credit for relevant queue management of data;
selecting at least one valid child element to retrieve from the queue according to the priority level of the queue transmission control data corresponding to the aforementioned valid child element;
adding credits to the credit balance corresponding to the amount of data retrieved from a queue; and where each valid and workable child element is present in one of the queues management of data.

17. The method according to clause 16, where the queue transmission control data include all positive credit transfer, all negative credit transfer and the extreme negative credit transfer and where:
the first threshold counter credit between all positive credit transfer and turn negative credit transfer is equal to zero;
the second threshold counter credit between all negative credit transfer and foremost extreme negative credit transfer is equal to the negative value of the maximum transmission unit to the data network;
all positive credit transfer has a higher priority in the choice of h is m turn negative credit transfer; and all negative credit transfer has a higher priority in selecting than all extreme negative credit transfer.

18. The method according to 17, where the queue management of data additionally include all extreme positive credit transfer and crawl queue:
all extreme positive credit transfer has a higher priority than the queue positive credit transfer, all negative credit transfer and the extreme negative credit transfer; and
crawl queue has the highest priority level and when transferring from the queue traversal loans in the loan balance will not be returned.

19. The method according to 17, where the queue management of data additionally include all unknown child elements, all unknown child elements containing a valid child element, activated by the parent scheduler to transfer the credit situation of the current scheduler.