Abstract:
An apparatus and method for generating via integer calculations a metric for estimating link utilization within a network device having at least one output port. The metric is determined by calculating at least three data rate link parameters for a given sampling period. The data rate link parameters include an error data rate parameter, an average data rate parameter, and a deviation data rate parameter. These parameters are determined using integer values and integer operations and may be used by a link management system for performing load balancing among a plurality of output ports and for determining whether to forward low priority data traffic via a particular output port.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS  
         [0001]    N/A  
         STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT  
         [0002]    N/A  
         BACKGROUND OF THE INVENTION  
         [0003]    This invention relates to computer data network devices and in particular to measuring various performance metrics of and controlling data routing within the data network devices based on the measured performance metrics.  
           [0004]    As computer networks continue to grow in size and capacity, data stream management systems are needed to ensure that data is not lost due to a link that is carrying an excessive amount of data. In particular, a data stream management system will need data rate information and other link-usage parameters in order to provide optimal, or near optimal, link allocation for data transmission thereon. The use of data stream management systems will allow more efficient use of link resources by allowing data to be transmitted over links that are currently being used at a level that is less than their overall capacity. In addition, a data stream management system can allow the reallocation of available bandwidth to lower priority signals when higher priority signals are not being transmitted, allowing increased revenue for the data carriers. Currently data stream management systems utilize complex statistical models that are implemented in software to derive the link-usage parameters. These statistical models typically require a large amount of historical data to produce acceptable results. As this historical data is gathered the statistical model either does not operate, or operates inaccurately. Accordingly, a loss of data can result during this time. In addition, the current software based systems use floating point operations which can result in slower calculations.  
           [0005]    Accordingly it would be advantageous to provide a hardware based data stream management system that has a shorter time constant for producing useful output and is able to capture more data and provide an accurate second quarter estimate of the data link parameters.  
         BRIEF SUMMARY OF THE INVENTION  
         [0006]    An apparatus for estimating link utilization within a network device having at least one output port is disclosed in which an integer counter is associated with the at least one output port and the integer counter is incremented in response to a predetermined event associated with the transmission of data through the output port. The integer counter is sampled periodically to determined the quantity of data transmitted through the at least one output port within a sampling period. For each sampling period an error value equal to the quantity of data minus a historical mean value corresponding to the mean value of data transmitted from the at least one output port during prior sampling periods is calculated. Also for each sampling period a current mean value equal to the historical mean value plus the product of a first predetermined multiplier times the error value is calculated, and a current deviation value equal to a historical deviation plus the product of a second predetermined multiplier multiplied by the difference of the absolute value of the error value minus the historical deviation value is also calculated. The error value, the current mean value, the historical mean value, and the current deviation value are all integer values.  
       
    
    
     BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS  
       [0007]    [0007]FIG. 1 is a block diagram depicting one embodiment of the present invention;  
         [0008]    [0008]FIG. 2 is a block diagram depicting a second embodiment of the present invention;  
         [0009]    [0009]FIG. 3 is a flow chart depicting a method for estimating link utilization for routing additional data streams; and  
         [0010]    [0010]FIG. 4 is a flow chart depicting a method for determining whether to include low priority data traffic in an additional data stream. 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0011]    [0011]FIG. 1 and FIG. 2 depict two block diagrams of an apparatus and corresponding method for managing and routing data streams to one or more output ports having one or more output links. As depicted in FIG. 1, an output port  102  includes a plurality of output links  104 ,  106 , and  108 . Each of the output links  104 ,  106 , and  108  includes an integer counter  110 ,  112 , and  114  associated therewith. Each of the integer counters is incremented in response to a predetermined event associated with transmission of data to the respective link. Each of the integer counters  110 ,  112 , and  114  have a corresponding sample logic module  116 ,  118 , and  120  associated therewith. The sampling logic periodically samples the integer counter and latches the integer count contained therein. The integer count is provided to a calculation logic  122 . The calculation logic  122  uses the data rate information from each link to determine the link usage parameters associated with the particular link. In particular, the link calculation logic  122  determines a mean data rate value, a data rate error value, and a deviation error value for the corresponding link. As will be explained in more detail below, the calculation logic  122  provides one or more of these determined link usage parameters to a port routing logic  124  that is used to route an incoming data stream  101  to a particular link.  
         [0012]    The sampling logic  116 ,  118 , and  120  are used to periodically sample the integer counter  110 ,  112 , and  114  associated therewith at a particular sample rate. In general the data stream is divided into a series of consecutive time slots, wherein the integer counter is sampled at substantially the same point within each timeslot. The selection of a timeslot size is a system specific parametric and is determined by the counter size, the size of a data input memory data buffer, and the data rate. In general, the data input memory buffer is able to absorb some variation in the data throughput rate, such that the timeslot size and sample period should be selected to avoid deviations in data rate that are unable to be absorbed by the buffer.  
         [0013]    The calculation logic  122  first determines an error value for timeslot “n” that is equal to the quantity of data transferred in the timeslot minus the historical mean data rate value, i.e., the mean data rate value as determined in the previous timeslot. The current mean data rate value is equal to the mean data rate value of the previous timeslot minus the error value of the current timeslot times a first predetermined multiplier. The current deviation data rate value is equal to the deviation value of the previous timeslot plus the product of a second predetermined multiplier multiplied by the difference of the absolute value of the error value of the current timeslot minus the deviation value of the previous timeslot. These equations are illustrated below.  
           Err   n   =A   n   −M   n−1    (1)  
           M   n   =M   n−1 −( h*Err   n )   (2)  
           D   n   =D   n−1   +g *(| Err   n   |D   n−1 )   (3)  
         [0014]    where n is the current time slot and n—1 is the previous time slot, and h and g are typically negative powers of two. In general h is greater than g. In a preferred embodiment h is equal to ¼ th  and g is equal to ⅛ th . Accordingly, the preferred embodiment of the system is able to advantageously provide data in a more timely fashion than current systems that use floating point calculations by using integer calculations.  
         [0015]    Each link therefore has associated therewith an estimated mean and an estimated deviation of the data rate through the link that may be used by a data stream management system. In particular, a data stream management system can include routing logic that receives a data stream as an input and provides a portion of that data stream to a predetermined port or link, wherein the port or link is selected as a function of the current mean data rate value and the current deviation data rate value of the available port or link. In particular, a bandwidth metric for each port or link may be determined by adding the current mean data rate value to the product of a third predetermined multiplier, “k”, and the current deviation data rate value. This is equivalent to expressing the data rate value within a selected confidence interval, such that for a particular value of k, the probability that the mean data rate value will be within that range is predetermined. For example, for k=1 the mean data rate value will be within plus or minus one deviation of the calculated value with a probability of approximately 0.7. For k=2, the probability that the mean data rate value will be within the particular confidence interval that is plus or minus two deviations of the mean data rate value with a probability that is approximately 0.95, and for k=3, the probability that the data rate mean value will be within the confidence interval that is plus or minus three deviations of the mean data rate value with a probability that is 0.99. Thus, the bandwidth metric calculated above can be used as an estimate of the traffic carried on a particular link within specific confidence intervals.  
         [0016]    Using the above calculated metric, load balancing may be performed by the data stream management system. In particular, data rate estimators, i.e., the mean data rate value and a deviation data rate value are calculated for each link and the utilized bandwidth metric described above is calculated for each link as well. When a data stream is received by the routing logic, the routing logic is provided with the utilized bandwidth metrics calculated for each of the links connected thereto. The routing logic is configured and arranged such that the incoming data stream is routed to the link having the lowest utilized bandwidth metric as calculated using the methods described above. In this way the incoming data stream is provided to the link having the most available bandwidth out of the selection of links. In one embodiment, a value of k=3 is used to provide a confidence interval as described above of approximately 0.9973. Selecting a higher confidence interval, i.e., selecting a larger value of k, allows for a higher probability that the particular link will be able to handle the bandwidth and data rate of the switched traffic and that there is a lower probability that the particular link will be blocked or otherwise overtaxed and result in the loss of data. In the event that two links have the same value of the bandwidth metric calculated above, a predetermined criteria can be used to select which of the two links receives the data stream.  
         [0017]    [0017]FIG. 2 depicts another embodiment of the presently described data stream management system  200  in which data rate parameters are determined for one or more output ports each of which includes a plurality of links associated therewith. The data rate parameters calculated for each output port are used to route additional data streams to a particular output port but not necessarily to an individual link within that port.  
         [0018]    In particular, as depicted in FIG. 2, the plurality of output ports  202 ,  204 , and  206  each include a link routing module  208 ,  210 , and  212  respectively, and a plurality of links associated with each output port and coupled to the respective link routing module. In particular, port  202  includes links  201 ,  203 , and  205 , port  204  includes links  207 ,  209 , and  211 , and port  206  includes links  213 ,  215 , and  217 . Each port  202 ,  204 , and  206  has associated therewith an integer counter  214 ,  216 , and  218  respectively that receives an incoming data stream  218  from port routing logic  228 . Each counter  214 ,  216 , and  218  has associated therewith sampling logic  220 ,  222 , and  224  respectively. The integer counters each respond to a predetermined event associated with a transmission of data by incrementing its internal counter. The sampling logic is configured and arranged to periodically sample the corresponding integer counter and to provide this data count to a calculation logic  226 . The calculation logic  226  determines parameters associated with each output port and provides this data to the port routing logic  228 .  
         [0019]    In particular, the calculation module  226  determines the aggregate port parameters using equations 1, 2, and 3 above. In one embodiment, the calculation logic module  226  also computes the bandwidth metric as described above for each port. The calculation module then subtracts the bandwidth metric for each port from the total available bandwidth of that port and provides this difference for each port to the port routing logic  228 . The port routing logic  228  receives an incoming data stream and switches this incoming data stream to the port having the largest difference value calculated above. In this way, the port routing logic  228  switches the incoming data stream to the output port having the largest available bandwidth. By selecting k sufficiently large in the formula above for the bandwidth metric, i.e., 3 or 4, a large confidence interval of the upper and lower values of the data is established. Thus, there will be a high probability that the average data rate for the corresponding port will be within the upper and lower values determined by the end points of the confidence interval. Accordingly, a higher probability can assure that the particular output port will not need extra bandwidth above that which has been already allocated. Therefore based on the upper and lower end points determined above, lower priority data may be transmitted through a port that has been reserved for higher priority data with a high probability that the port will not be overtaxed with the concomitant loss of data and blockage. In this way, telecom and data service providers may utilize these data links for other, lower priority traffic. This allows the telecom and data service providers an opportunity to increase the revenue available from these data links by utilizing more of the available bandwidth with a high degree of confidence that the lower priority data added to the link will not result in the blockage and potential loss of higher priority data.  
         [0020]    [0020]FIG. 3 depicts a flow chart illustrating a method for generating a plurality of metrics indicative of link utilization via integer operations for use in load balancing. In particular, a plurality of output ports receives a corresponding plurality of data streams, as depicted in step  300 . Each data stream is transmitted from the corresponding output port, as depicted in step  302 . For each of the plurality of output ports, an integer counter associated with the respective output port is incremented in response to the transmission of the data stream from the output port, as depicted in step  304 . For each of the plurality of output ports, the respective integer counters is periodically sampled and a value indicative of the quantity of data transmitted through the respective output port is obtained, as depicted in step  306 . For each of the plurality of output ports, the metric is calculated from a current error value, a current mean value, and a current deviation value as discussed above and as depicted in step  308 . More specifically, the current error value is equal to the quantity of data transmitted through the respective output port in the last sampling period minus a historical mean value of the data transmitted through the respective output port over one or more sampling periods. The current mean value is equal to the historical mean value of the data transmitted through the respective output port over one or more sampling periods plus the product of a first predetermined multiplier times the current error value of the respective output port. The current deviation value is equal to a historical deviation value, which is the deviation value over one or more sampling periods, plus the product of a second predetermined multiplier multiplied by the difference of the absolute value of the current error value for the respective output port minus the historical deviation value for the respective output port. Based on the metrics for the respective ports, a determination may be made as to which output port the next incoming data stream is to be routed, as depicted in step  310 .  
         [0021]    [0021]FIG. 4 depicts a flow chart illustrating a method for generating at least one metric indicative of the link utilization via integer operations for assigning unused transmission bandwidth. In particular a data stream is received by an output port, as depicted in step  400 . The data stream is transmitted from the output port, as depicted in step  402 . An integer counter associated with the output port is incremented in response to the transmission of the data stream from the output port, as depicted in step  404 . The integer counter is sampled and a value indicative of the quantity of data transmitted through the output port during the sampling period is obtained, as depicted in step  406 . A metric is generated for the output port, based on a current error value, a current mean value, and a current deviation value, as depicted in step  408 . The current error value is equal to the quantity of data transmitted through the output port in the last sampling period minus a historical mean value of the data transmitted through the port over one or more sampling periods. The current mean value is equal to the historical mean value of the data transmitted through the output port over one or more sampling periods plus the product of a first predetermined multiplier times the current error value. The current deviation value is equal to a historical deviation value, which is the deviation value of the output port over one or more sampling periods, plus the product of a second predetermined multiplier multiplied by the difference of the absolute value of the current error value minus the historical deviation value. The metric indicative of link utilization is generated as discussed above. Based on the link utilization metric, a determination is made as discussed above, whether lower priority data traffic is to be transmitted via the output port.  
         [0022]    Those of ordinary skill in the art should further appreciate that variations to and modifications of the above described methods and apparatus for data stream management system and method can be made. Accordingly, the invention should not be viewed as limited except by the scope and spirit of the appended claims.