Abstract:
A computer based system and method for distributing a global shaper rate implemented across multiple traffic processing devices. A controller distributes credits according to the demand (amount of traffic, or offered load) of each device, in such a way to achieve global targets, including the shaper rate, strict prioritization of traffic, WFQ weights and fairness between cloned channels, iteratively updated as changes occur in the quantity and makeup of the traffic across the devices

Description:
FIELD 
       [0001]    The present application relates to the computer field of “traffic shaping”. Traffic shaping is used to manage the bandwidth on a communications network to meet performance goals. Traffic shaping is a process of optimizing traffic by examining attributes of packets and delaying or dropping certain packets in order to achieve goals such as: attaining specific bitrates, attaining specific ratios between different types of traffic, providing fair sharing of bandwidth or smoothing bursts of traffic. 
       BACKGROUND 
       [0002]    Traffic shaping deals with datagram traffic (a stream of datagram packets) from one or many source computers to one or many destination computers. A traffic shaper lies between the source and the destination of each packet of the traffic. The traffic is prioritized by the shaper, and based on this, a decision is made for each packet whether it is delivered to the destination or not, as well as when it is delivered. 
         [0003]    In a typical solution, a traffic shaping deployment may include multiple traffic processing devices, each shaping a portion of the traffic. The quantity or makeup of traffic going to each device may not be the same, which means that simply dividing the desired values by the number of devices and allowing each device to shape the traffic independent of the others will not be sufficient to achieve the performance goals. 
         [0004]    Deriving the solution for the correct rates and parameters to achieve performance goals is non-trivial. This cannot generally be done manually as the quantity and makeup of traffic in each traffic processing device is constantly changing. As such, there is a need for an improved method, system and apparatus for managing a shaper or shapers. 
       SUMMARY 
       [0005]    Embodiments herein are intended to address the need for achieving traffic shaping performance goals by coordinating shaping behavior on multiple traffic processing devices using iterative re-evaluation and updating of the parameters applied to shapers on each traffic processing device. 
         [0006]    According to one aspect herein, there is provided a computer based system and method for distributing a global shaper rate implemented across multiple traffic processing devices. In particular, a controller distributes credits according to the demand (amount of traffic, or offered load) of each traffic processing device, in such a way to achieve global targets, including the shaper rate, strict prioritization of traffic, WFQ weights and fairness between cloned channels, iteratively updated as changes occur in the quantity and makeup of the traffic across the devices. 
         [0007]    In an aspect of embodiments herein, there is provided a system for monitoring and modifying the behavior of a plurality of shapers, the system including: a server, residing on a controller; and a plurality of clients in communication with the server, each of the clients residing on one or more traffic processing devices and the clients configured to monitor datagram traffic, wherein the server is configured to receive statistics related to the datagram traffic from the clients and to retain the same; and the server is configured to utilize the statistics to send commands to the clients to modify the behavior of the shapers. 
         [0008]    In a particular case, the commands may instruct the clients to provide a new maximum rate for a priority related to at least one of the shapers. 
         [0009]    In another particular case, the commands may instruct the clients to provide a new weight for a channel related to at least one of the shapers. 
         [0010]    In yet another particular case, the commands may instruct the clients to assign a total rate to each of the multiple shapers. 
         [0011]    In another aspect, there is provided a method for monitoring and modifying the behavior of a plurality of shapers, the method including: for each shaper: and for each priority of the shaper: a) determining a demand sum for an instance and priority; b) determining a weight sum for the priority; c) determining a rate for the priority; and d) determining a channel weight for the priority, wherein the determining utilizes data provided by a statistics record related to the shaper; and generating a command record for delivery to each shaper to modify the behavior of the shapers. In particular, the command record may be a message containing new parameters for the shaper in order to make the shaper more efficient based on current operating conditions. 
         [0012]    In a particular case, the demand sum comprises the sum of demand across all clients for a shaper. 
         [0013]    In another particular case, the weight sum comprises the sum of the weights of all channels in a given priority. 
         [0014]    In yet another particular case, the rate for a priority comprises an allocated rate for an instance priority pair, divided by a demand ratio. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0015]    Embodiments will now be described, by way of example only, with reference to the attached Figures, wherein: 
           [0016]      FIGS. 1A and 1B  are block diagrams of shaper instances, each cloned from the same shaper; 
           [0017]      FIG. 2  is a block diagram of an embodiment herein; 
           [0018]      FIG. 3  is a block diagram of the hierarchical data utilized by a controller to identify the components associated with a system of shapers; 
           [0019]      FIG. 4  is a block diagram of a variable length statistics data record; 
           [0020]      FIGS. 5A and 5B  are block diagrams of an example of a series of variable length statistics data records; 
           [0021]      FIG. 6  is a block diagram of a variable length command data record; 
           [0022]      FIGS. 7A and 7B  are block diagrams of an example of a series of variable length command data records; 
           [0023]      FIGS. 8 to 13  are flowcharts of methods used to analyze statistics and generate commands. 
       
    
    
     DETAILED DESCRIPTION 
       [0024]    A user creates a “policy definition” which defines a shaper. A policy definition is the template information for a shaper. A shaper has one or more priorities, each priority having one or more channels. Each shaper may have a unique-by variable associated with it, which defines the shaper instances. Each priority may have a shared-by variable associated with it which defines the channel instances. 
         [0025]    A number of schemes may be utilized in shaping traffic to meet performance goals. Schemes may be combined and typically utilize “credits” (which represent a binary “bit” of traffic) to determine when a packet may be sent. In every case, credits are created at a constant rate, and if and only if a “channel” has enough credits, a packet is sent. Examples of schemes for allocating credits follow:
       1) Cloned shaping or “unique-by” shaping. This scheme involves dynamically making a clone of a shaper on demand, for each unique value of an input variable. For example, creating a shaper for each different service tier level of the subscribers as the different levels are in use, creating a shaper for each IP address, or creating a shaper for each of some shared network resource such as a physical link or transmission frequency. Each cloned shaper, called a “shaper instance”, shapes its traffic to the configured shaper rate.   2) Traffic can also be strictly prioritized, wherein credits are first given to the highest priority, and then the unused credits of a priority are made available to the next highest priority.   3) Weighted Fair Queuing (WFQ). In contrast to strict prioritization, a client allocates credits to each channel proportional to the weight of the channel. For example, a channel of weight 2 receives twice as many credits (and consequently, sends twice as many bits of traffic) as a channel of weight 1. Unused credits of one channel may be used by other channels.   4) Fair shaping, or “shared-by” shaping, involves making a clone of a channel for each unique value of an input variable. For example, a channel could be cloned for every unique sender IP-address. A traffic processing device then divides the credits equally among the cloned channels, called “channel instances”, thus giving each a fair share of the traffic. This is fundamentally the same as WFQ, save that channels are dynamically added and removed and each channel has equal weight.       
 
         [0030]    An example policy definition for creating a shaper comprising two shaper instances as shown in  FIGS. 1A and 1B  is attached as Appendix “A”. 
         [0031]    With reference to  FIGS. 1A and 1B , credits move from right to left. Datagram traffic is sent via a channel instance such as feature  20 . 
         [0032]    As discussed earlier, a shaper  10  may have many instances such as gold  12  or bronze  14 .  FIGS. 1A and 1B  when combined define a shaper  10 . Each instance is cloned based on a unique-by variable such as service tier configurable by the user. At each time interval, a shaper instance ( 12 ,  14 ) creates credits. The number of credits created is determined by the rate the shaper instance is configured to attain. The credits are passed to a priority ( 16 ,  18 ,  48 ,  50 ). Here we show two shaper instances, each representing a service tier. Instance  12  is a gold level shaper instance, meaning it shapes traffic for subscribers in the gold service tier. In contrast shaper instance  14  is a bronze level shaper instance, and as such shapes traffic for subscribers in the bronze service tier. Both instances  12  and  14  independently shape at a configured rate, which may be the same rate. As can be seen from  FIG. 1B  the features are identical to that of  FIG. 1A  save that they are associated with a different shaper instance. 
         [0033]    The features  36  and  38  refer to subscribers, each being assigned as a value of the shared-by variable. A subscriber may be a single IP address or multiple IP addresses belonging to the same customer. Each subscriber may have multiple channel instances, typically one for each channel. By way of example, Sub  1  ( 36 ) of  FIG. 1A  has channel instances  20 ,  22 ,  24  and  26 . 
         [0034]    Within a shaper instance, there may be a plurality of priorities, the exact meaning of each is configurable by the user. In the example of  FIG. 1A , priority level  16  is rated as “high”, while priority level  18  is rated as “low”. In this case, this means “low” will only receive credits that “high” does not use. The priorities ( 16 ,  18 ) in turn take their credits and give them to the channel instances, for example ( 20 - 34 ) under them. 
         [0035]    Each channel is assigned a weight, configurable by the user, and each channel instance cloned from that channel is given that weight. For example, channel instances (sub 1   20 , sub n  28 ) are clones of the channel for VOIP  40 , of weight five. Channel instances (sub 1   24 , sub n  32 ) are instances of a channel  44  for web traffic, of weight three. These channels are shown by way of example. Many different channels may be added with weights for specific traffic. Different weighted channels are made for different protocols in this case, but not necessarily always. Some configurations, for example, may provision different weighted channels for different classes of customers. For example, a deluxe level of service of weight ten, a normal level of service, of weight five, and an economy level of service, of weight two. 
         [0036]    A channel may have multiple instances, typically one for each unique value of the shared-by variable. This is shown as features Sub  1  ( 36 ) to Sub n ( 38 ). For example, a channel VOIP  40  is cloned for Sub  1  ( 36 ) to create channel instance  20 . The same channel is cloned for Sub n ( 38 ) to make channel instance  28 . Note that the number of channel instances is determined by the shared-by variable, and may not be the same for different shaper instances of the same shaper. The channel instances receive datagram packets and determine if packets are delivered, delayed or dropped according to available credits. 
         [0037]    Referring now to  FIG. 2  a block diagram of an embodiment of a system herein is shown. 
         [0038]    An implementation consists of four types of modules, based upon a client-server model. As one skilled in the art will appreciate the function of each module may be distributed or combined between modules. By way of example we describe an implementation of a basic system. 
         [0039]    The modules of  FIG. 2  comprise: controller  94 , traffic processing devices  96   a,    96   b ), clients ( 98   a,    98   b ) and server  99 . Clients ( 98   a,    98   b ) residing on the traffic processing devices ( 96   a,    96   b ) communicate with server  99 , residing on controller  94 . 
         [0040]    Server  99  receives statistics ( 100   a,    100   b ) and transmits commands ( 102   a,    102   b ) to clients ( 98   a,    98   b ). Each traffic processing device ( 96   a,    96   b ) receives datagram packets ( 90   a,    90   b ). Depending on the configuration, a packet may be passed to a channel instance inside a shaper, and depending upon available credits, it may be dropped, delivered or queued for future delivery. The delivery of packets is shown by features  92   a  and  92   b.    
         [0041]    Traffic processing devices ( 96   a,    96   b ) are typically computing devices upon which a software client ( 98   a,    98   b ) may reside as a separate computing thread. In one embodiment there may be one or more clients each handling a subset of the traffic going to a traffic processing device. Controller  94  is typically a computing device upon which a software server  99  may reside as a separate computing thread. It will be understood that the traffic processing devices, controller, server and clients may be embodied in hardware or software. In some cases, these elements may be co-located while in others they may be distributed both physically and logically. Where implemented as software, these elements may be provided as physical computer-readable media containing computer-readable instructions, which, when executed on a computing device, which may be a dedicated device, cause the device to perform the functions of the respective feature. 
         [0042]    A client ( 98   a,    98   b ) runs parallel to its traffic processing device ( 96   a,    96   b ), and serves at least two purposes:
       1) to collect detailed statistics about the datagram traffic ( 90   a,    90   b ) passing through a traffic processing device ( 96   a,    96   b ) and to send those statistics ( 100   a,    100   b ) to server  99 ; and   2) to accept commands ( 102   a,    102   b ) from the server  99  and inform a traffic processing device ( 96   a,    96   b ) to adjust the parameters of a shaper instance such as feature  12  of  FIG. 1A  (for example, the rate for the shaper instance  12 , or the modification of the weights of all channel instances cloned from channel  40 ).       
 
         [0045]    Referring now to  FIG. 3 , a block diagram of the hierarchical data utilized by a controller to identify the components associated with a system of shapers is shown. We also refer the reader to  FIGS. 1A and 1B  which illustrate instances of shapers. 
         [0046]    A shaper  10  is defined by a policy as discussed above with reference to Appendix “A”. A shaper  10  may be utilized by a plurality of traffic processing devices such as  96   a  and  96   b  (see  FIG. 2 ). For each shaper  10 , a traffic processing device ( 96   a,    96   b ) has a plurality of shaper instances, such as  12 , according to the unique-by values. Each shaper instance ( 12 ,  14 ) has a plurality of priorities such as  16 . Associated with each priority may be one or more channels, such as  40 . Channels in turn may have one or more channel instances, according to the shared-by values, as shown for example as features  20  and  28  of  FIG. 1A . 
         [0047]    Referring now to  FIG. 4  a block diagram of a variable length statistics data record is shown. A statistics record is shown as features  100   a  and  100   b  of  FIG. 2 . There are four types of sections in each statistics record. They are sections  110 ,  112 ,  114 ,  116 . 
         [0048]    The first field of each section is a unique identifier for that section, e.g. each shaper definition is given a shaper ID  110   a.  Each shaper instance is given an Instance ID  112   a.  Each priority is given a Priority ID  114   a.  Each channel is given a Channel ID  116   a.  The last field ( 110   b,    112   d  and  114   d ) of each section, excluding the field  116   d,  indicate how many instances of the following sub-section are present for that record, e.g. the field  112   d  indicates the number of priorities present in this statistics record for the shaper instance. The field  116   d  indicates a maximum bandwidth or load a channel is requesting. 
         [0049]    Current rate  112   b  is the current value for the rate of a shaper instance. Current Max Rate  114   b  is the current value for the maximum rate of a priority. Current weight  116   b  is the current value for the weight of a channel. Current weight  116   b  is stored in all the channel instances for a channel. Each channel instance for a channel generally has the same weight, so the current weight  116   b  is the weight for a channel, representing all of its channel instances. In other words, statistics are generally sent for a channel, not individual instances. 
         [0050]    Demand metrics  112   c,    114   c  and  116   c  indicate how much datagram traffic is being handled. For example, a doubling of traffic would effect a doubling of the demand. This can be expressed in various metrics, one being an input bit rate. 
         [0051]    Referring now to  FIGS. 5   a  and  5   b  block diagrams of an example of a series of variable length statistics data records is shown. 
         [0052]    Section  118  indicates there are two instances of a shaper having a Shaper ID of “0”. Each section  120  describes one of these two instances. Each section  120  includes a current rate  120   b,  and a demand metric  120   c.  Current Rate  120   b  is the rate for a shaper instance (shown here in Mbps). The demand metric  120   c  is the bits per second requested by the instance and in this example is the sum of the two demand metric fields  122   c  of priorities  122  associated with instance  120 , 
         [0053]    Each instance may have multiple priorities  122 . Each priority section  122  includes a current max rate  122   b  and a demand metric  122   c.  Current max rate  122   b  in this example is set to infinity. Demand metric  122   c  is the bits per second requested by the priority. 
         [0054]    Each priority may have multiple channel sections  124 . Each channel section  124  includes a current weight  124   b,  which is the current weight of all the channel instances for the specified channel. This is initially the target weight defined for the channel. For example in  FIG. 1A  channel  40  has two VOIP instances both having the same weight of five. Demand metric  124   c  may be the number of bits requested by a channel, unless the shaper is “shared-by”, in which case the demand metric  124   c  is the number of channel instances. In this example, a channel instance is created for a subscriber, so the number of channel instances for a channel equals the number of subscribers. Offered load  124   d  is the number of bits per second requested by the channel. 
         [0055]    Referring now to  FIG. 6  a block diagram of a variable length command data record is shown. 
         [0056]    The structure of  FIG. 6  indicates the format of command messages ( 102   a,    102   b ) sent by server  99  to clients ( 98   a,    98   b ), as shown in  FIG. 2 . Each command message comprises a section  130  which identifies a shaper ID  130   a  and the number of instances  130   b  of that shaper ID. 
         [0057]    For each shaper instance of a shaper with ID  130   a,  a section  132  exists. Section  132  comprises an instance ID  132   a  to identify the shaper instance. New level setting  132   b  represents the new rate for the shaper instance. Number of priorities  132   c  indicates the number of priorities for a shaper instance, each priority having a section  134 . Section  134  comprises a field  134   a  which identifies the priority. Field  134   b  indicates a new maximum rate for the priority. Field  134   c  indicates the number of channels associated with priority ID  134   a.  Finally, section  136  exists for each channel ID  136   a  and provides a new weight  136   b.    
         [0058]    Referring now to  FIGS. 7A and 7B , block diagrams of an example of a series of variable length command data records is shown. 
         [0059]    Section  138  indicates there are two instances of a shaper having a Shaper ID of “0”. Each section  140  describes a shaper instance of the shaper. An instance section  140  includes a new rate value  140   b  which defines what the new rate for the shaper instance should be set to. Each instance section  140  may have multiple priority sections as shown by sections  142 . Each priority section  142  includes a new maximum rate  142   b  to be set for the priority. 
         [0060]    Each priority may have multiple channels. Each channel section  144  includes a new weight in field  144   b  for the channel. The values shown in field  144   b  may be large numbers (where 1000s are denoted with the symbol ‘k’) or small numbers. In this embodiment, since the absolute values of the weights are insignificant, and only the ratios are significant, a weighting of 250 k to 400 k is the same as a weighting of 25 to 40 (which could be further simplified to 5 to 8). 
         [0061]    As statistics ( 100   a,    100   b ) arrive to the server ( 99 ), they are stored in a data structure, which is used for the calculation of commands ( 102   a,    102   b ). One embodiment of such a data structure follows. Data type details have been omitted (e.g. int32/int64, signedness, rounding errors). 
       Data Structure 1 
       [0062]      
         [0000]    
       
         
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 struct channel { 
               
               
                   
                   int weight; 
               
               
                   
                   int demand; 
               
               
                   
                   int load; 
               
               
                   
                 }; 
               
               
                   
                 struct priority { 
               
               
                   
                   int max_rate; 
               
               
                   
                   int demand; 
               
               
                   
                   channel channels[num_channels]; 
               
               
                   
                 }; 
               
               
                   
                 struct instance { 
               
               
                   
                   int rate; 
               
               
                   
                   int demand; 
               
               
                   
                   priority priorities[num_priorities]; 
               
               
                   
                 }; 
               
               
                   
                 struct client { 
               
               
                   
                   instance instances[num_instances]; 
               
               
                   
                 }; 
               
               
                   
                 struct shaper { 
               
               
                   
                   client clients[num_clients]; 
               
               
                   
                 }; 
               
               
                   
                 shaper shapers[num_shapers]; 
               
               
                   
                   
               
             
          
         
       
     
         [0063]    The statistic values and those stored in the data structure are generally the same. These values are manipulated by the server  99 , to generate command values. The following Table 1 illustrates an example correlation of the various values. 
         [0000]    
       
         
               
             
               
               
               
               
             
           
               
                 TABLE 1 
               
             
             
               
                   
               
               
                 Correlation of Values 
               
             
          
           
               
                   
                 Statistics 
                 Data Structure 
                 Command Value 
               
               
                   
                   
               
               
                   
                 Current rate 
                 instance.rate 
                 New level 
               
               
                   
                 Current max rate 
                 priority.max_rate 
                 New max rate 
               
               
                   
                 Current weight 
                 channel.weight 
                 New weight 
               
               
                   
                 Offered load 
                 channel.load 
               
               
                   
                 Demand metric 
                 X.demand 
               
               
                   
                 Number of X 
                 X.num_X 
               
               
                   
                   
               
             
          
         
       
     
         [0064]    In the above Table 1, the value X can be substituted for one of: instance, priority or channel. For example “Number of Channels” would be “channel.num_channels”. 
         [0065]    The keys to the arrays of each structure are generally the various IDs: Channel ID, Priority ID, Instance ID, Client ID, and Shaper ID. 
         [0066]    Referring now to  FIGS. 8 to 13 , flowcharts of methods used to analyze statistics and generate commands are shown. 
         [0067]    The methods illustrated in  FIGS. 8 to 13  cycle through the features of  FIG. 3 , such as shapers  10 , traffic processing devices  96   a  (sometimes referred to as an “agent”), shaper instances  12 , priorities  16  and channels  40 . 
         [0068]    To aid the reader in better understanding the flowcharts of  FIGS. 8 to 13  following table describes the variables used. 
         [0000]    
       
         
               
             
               
               
             
           
               
                 TABLE 2 
               
             
             
               
                   
               
               
                 Variable Name Definitions 
               
             
          
           
               
                 Name 
                 Definition 
               
               
                   
               
               
                 allocated_rate[i][p] 
                 The amount of bandwidth assigned to a client per shaper 
               
               
                   
                 instance and priority. (i = instance, p = priority) 
               
               
                 bw_remaining 
                 The bandwidth remaining to be allocated to a set of channels. 
               
               
                 channel.load 
                 The offered load in the statistics record (116d) 
               
               
                 channel.weight 
                 The current weight from the statistics record (116b), 
               
               
                   
                 initially the weight defined in the policy for this channel. 
               
               
                 demand_ratio 
                 priority.demand/demand_sum[i][p] 
               
               
                 demand_sum[i][p] 
                 Sum of demand across all clients for a shaper instance, 
               
               
                   
                 priority pair (i = instance, p = priority). 
               
               
                 new_channel.new_level 
                 The new weight in the command record (136b) 
               
               
                 new_instance.new_level 
                 The new level in the command record (132b) 
               
               
                 new_level 
                 The portion of the bandwidth remaining which is to be 
               
               
                   
                 assigned to the current channel in this iteration. 
               
               
                 new_priority.new_level 
                 The maximum rate in the command message (104.b) 
               
               
                 priority.demand 
                 The demand metric for the current priority from a statistic 
               
               
                   
                 record (114c) 
               
               
                 priority.max_rate 
                 The maximum rate from a statistics message (114b), 
               
               
                   
                 initially the max_rate defined in the policy for this priority. 
               
               
                 priority_rate 
                 allocated_rate[i][p] * demand_ratio 
               
               
                 remaining[i] 
                 The amount of remaining (unallocated) credits for an 
               
               
                   
                 instance, (i = instance). As credits are allocated to a 
               
               
                   
                 priority, this value is reduced accordingly. 
               
               
                 shaper.rate 
                 The rate defined in a policy for this shaper, i.e. the 
               
               
                   
                 desired target rate across the system. 
               
               
                 weight_sum[p] 
                 The sum of the weights on the channels in the given 
               
               
                   
                 priority (p = priority) 
               
               
                   
               
             
          
         
       
     
         [0069]    Referring first to  FIG. 8  processing begins at step  150 . The process beginning at step  150 , is initiated by server  99  in which the process resides. 
         [0070]    At step  152  a test is made to determine if all shapers have been examined. If there are no more shapers to examine, processing moves to step  154  and ends. If there are still shapers to examine the process moves to step  156 . The process of step  156  is detailed in  FIG. 9 . At step  156  instances and priorities are examined so that the value of demand_sum [i][p] may be set for each shaper instance, priority pair at step  158 . 
         [0071]    Processing then moves from step  158  to step  160  where the value of remaining[i] is set to shaper.rate. After step  160 , processing returns to step  156 . Once step  156  is completed, processing moves to step  161 . At step  161 , a weight calculation is made for each priority as shown in  FIG. 13 . At step  162  each priority is again examined as detailed in  FIG. 9 . In this iteration through the steps of  FIG. 9  the shaper instances and priorities are examined to determine the values used to establish the contents of a command message. 
         [0072]    For each priority examined, processing moves to step  166 . Once all priorities have been examined, processing returns to step  152 . At step  166  the value of allocated_rate[i][p] is set as shown in  FIG. 10 . Processing then moves to step  168 , where the priority rate is determined. Step  168  is detailed in  FIG. 11 . 
         [0073]    Upon completing step  168  processing moves to step  170  which is detailed in  FIG. 12 . Upon completion of step  170  processing moves to step  162 . 
         [0074]    We refer now to  FIG. 9 , which relates to step  156  and  162  of  FIG. 8 . At step  180  a test is made to determine if clients remain to be examined. If the test is negative, processing ends. If the test is positive, processing proceeds to step  182  where a test is made to determine if a shaper instance remains to be examined. If not, processing returns to step  180 . If a shaper instance remains, processing moves to step  184 . At step  184  a test is made to determine if a priority needs to be examined. If so, processing continues with steps  158  (from step  156 ) or  166  (from step  162 ). If the test at step  184  results in the negative, processing returns to step  182 . A link is also shown from steps  160  or  170  of  FIG. 8  where it connects to feature  184 . Note that  FIG. 9  has the same logic as that for step  156  and step  162  of  FIG. 8 . 
         [0075]    We refer now to  FIG. 10 , which relates to step  166  of  FIG. 8 . Step  166  determines how much traffic to give to a priority level, across all clients. Processing starts at step  192  where a test is made to determine if the allocated rate for each instance, priority pair is less than zero, i.e. whether it has been initialized or not. If it is non-negative (initialized), processing ends. If the rate is less than zero processing moves to step  194  where allocated_rate[i][p] is set to min(remaining[i], demand_sum[i][p], priority.max_rate). Processing then moves to step  196  where remaining[i] is reduced by the value of allocated_rate[i][p], after which processing ends. 
         [0076]    We refer now to  FIG. 11 , which relates to step  168  of  FIG. 8 . At this step the maximum rate for a priority on a client is calculated as a fraction of the total maximum rate for the priority, proportional to the demand for that priority on that client. At step  200 , the value of demand_ratio is set. At step  202  a test is made to determine if prority.max_rate is less than infinity. If so processing moves to step  204  where the value of new_priority.new_level is set. Here and throughout the figures, the prefix “new_” refers to a command value, while the lack of it refers to a statistics value. If the test at step  202  is negative processing moves to step  206  where the priority_rate is set. Processing then moves to step  208  where new_instance.new_level is increased by the priority_rate. Processing then ends and starts again ate step  170  of  FIG. 8 . 
         [0077]    We refer now to  FIG. 12 , which relates to step  170  of  FIG. 8 . In this step, credits are distributed to channels as necessary. Any credits assigned to a channel that exceed the credits requested by that channel are re-distributed to the other channels. Beginning at step  300  the value of bw_remaining is set to priority_rate. At step  302  a test is made to determine if the value of bw_remaining is greater than zero. If not, processing ends. 
         [0078]    If the value of bw_remaining is positive, processing moves to step  304  where a test is made to determine if there is a channel remaining to examine, If not, processing returns to step  302 . If a channel does remain to be examined, processing moves to step  306 . At step  306  a test is made to determine if the value of new_channel.new_level is less than the value of channel.load. If the test at step  306  is positive, processing moves to step  308 , where the value of new_level is set. If the test at step  306  is negative processing returns to step  304 . Upon completion of step  308  processing moves to step  310  where the value of new_channel_new_level is increased by new_level. Processing then moves to step  312  where a test is made to determine if the value of new_channel.new_level&gt;channel.load. If not processing moves to step  320 . If the test at step  312  is positive processing moves to step  314  where the value of new_level is set. Processing then moves to step  316  where the value of new_channel.new_level is set. Processing then moves to step  318  where the value of weight_sum[p] is decreased by the channel.weight. Processing then continues at step  320 , where the value of bw_remaining is decreased by the new_level and processing then returns to step  304 . 
         [0079]    We refer now to  FIG. 13 , which relates to step  161  of  FIG. 8 . At step  340  a test is made to determine if all priorities have been examined. If no priorities remain, processing ends. If priorities remain, processing moves to step  342  where a test is made to determine if all channels for a priority have been dealt with. If no, processing returns to step  340 . If yes, processing moves to step  344  where a weight sum for the priority is updated. Processing then returns to step  342 . 
         [0080]    Other aspects and features of the present invention will become apparent to those ordinarily skilled in the art upon review of the following description of specific embodiments of the invention in conjunction with the accompanying figures.