NETWORKTRAFFIC PREDICTOR AND METHOD

0Associated
Cases 
0Associated
Defendants 
0Accused
Products 
0Forward
Citations 
0
Petitions 
1
Assignment
First Claim
1. A method for predicting networktraffic bursts comprising:
 identifying, in data received by a networking device, a plurality of networktraffic bursts, each of the plurality of networktraffic bursts occurring at a respective one of plurality of bursttimes {t_{N}, t_{N1}, . . . , t_{0}}, N≥
3;
determining a timeinterval τ
_{n }of a next burst occurring at τ
_{n }after bursttime t_{1 }by determining respective values of predicted timeinterval τ
_{n}, a parameter ξ
, and a parameter η
that minimize, to within a tolerance, a quantity (f_{k }(ξ
, η
, k)−
(τ
_{n}−
t_{k})) for three values of a positive integer k≤
N, parameters ξ and
η
being, respectively, a real part and an imaginary part of a powerlaw exponent of a power law relating predicted timeinterval τ
_{n }to any of the plurality of bursttimes; and
determining, from a cumulative distribution function of a normal distribution of previouslyidentified networktraffic bursts occurring within a timeinterval that includes a previouslypredicted bursttime τ
_{p }similar to predicted timeinterval τ
_{n }by less than a predetermined tolerance, a timeduration during which the networking device may reallocate bandwidth according to at least one of traffic type, a subnet mask, and IP address.
1 Assignment
0 Petitions
Accused Products
Abstract
A method for predicting networktraffic bursts includes identifying, in data received by a networking device, a plurality of networktraffic bursts, each of the plurality of networktraffic bursts occurring at a respective one of plurality of bursttimes {t_{N}, t_{N1}, . . . , t_{0}}. The method includes determining a timeinterval τ_{n }of a next burst occurring at τ_{n }after bursttime t_{1 }by determining respective values of τ_{n}, a parameter ξ, and a parameter η, that minimize, to within a tolerance, a quantity (f_{k }(ξ, η, k)−(τ_{n}−t_{k})) for at least three values of a integer k. Parameters ξ and η are, respectively, a real and imaginary part of a powerlaw exponent of a power law relating predicted timeinterval τ_{n }to any of the plurality of bursttimes. The method includes determining, from a cumulative distribution function of a normal distribution of previouslyidentified networktraffic bursts, a timeduration during which the networking device may reallocate bandwidth.
0 Citations
No References
No References
18 Claims
 1. A method for predicting networktraffic bursts comprising:
identifying, in data received by a networking device, a plurality of networktraffic bursts, each of the plurality of networktraffic bursts occurring at a respective one of plurality of bursttimes {t_{N}, t_{N1}, . . . , t_{0}}, N≥
3;determining a timeinterval τ
_{n }of a next burst occurring at τ
_{n }after bursttime t_{1 }by determining respective values of predicted timeinterval τ
_{n}, a parameter ξ
, and a parameter η
that minimize, to within a tolerance, a quantity (f_{k }(ξ
, η
, k)−
(τ
_{n}−
t_{k})) for three values of a positive integer k≤
N, parameters ξ and
η
being, respectively, a real part and an imaginary part of a powerlaw exponent of a power law relating predicted timeinterval τ
_{n }to any of the plurality of bursttimes; anddetermining, from a cumulative distribution function of a normal distribution of previouslyidentified networktraffic bursts occurring within a timeinterval that includes a previouslypredicted bursttime τ
_{p }similar to predicted timeinterval τ
_{n }by less than a predetermined tolerance, a timeduration during which the networking device may reallocate bandwidth according to at least one of traffic type, a subnet mask, and IP address. View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
 10. A networktraffic burst predictor comprising:
a processor communicatively coupled to a networking device; and a memory storing nontransitory computerreadable instructions that, when executed by the processor, control the processor to; identify, in data received by a networking device, a plurality of networktraffic bursts, each of the plurality of networktraffic bursts occurring at a respective one of plurality of bursttimes {t_{N}, t_{N1}, . . . , t_{0}}, N≥
3;determine a timeinterval τ
_{n }of a next burst occurring at τ
_{n }after bursttime t_{1 }by determining respective values of predicted timeinterval τ
_{n}, a parameter ξ
, and a parameter η
that minimize, to within a tolerance, a quantity (f_{k }(ξ
, η
, k)−
(τ
_{n}−
t_{k})) for three values of a positive integer k≤
N, parameters ξ and
η
being, respectively, a real part and an imaginary part of a powerlaw exponent of a power law relating predicted timeinterval τ
_{n }to any of the plurality of bursttimes; anddetermine, from a cumulative distribution function of a normal distribution of previouslyidentified networktraffic bursts occurring within a timeinterval that includes a previouslypredicted bursttime τ
_{p }similar to predicted timeinterval τ
_{n }by less than a predetermined tolerance, a timeduration during which the networking device may reallocate bandwidth according to at least one of traffic type, a subnet mask, and IP address. View Dependent Claims (11, 12, 13, 14, 15, 16, 17, 18)
1 Specification
This application claims benefit of priority to U.S. Provisional Patent Application Ser. No. 62/652,786, filed on Apr. 4, 2018, which is incorporated herein by reference.
Efficient allocation of bandwidth across a communication network is an important contributor to the network'"'"'s quality of service (QoS) to its users. Intermittent bursts in network traffic poses a challenge to efficient bandwidth allocation, as communication channels experiencing such bursts have fluctuating bandwidth requirements. Allocating too little bandwidth to a channel results in sluggish data transmission when bursts occur. Allocating the channel sufficient bandwidth to accommodate bursts is inefficient, as the channel does not utilize its full bandwidth during relatively low datarate periods occurring between bursts.
In a first aspect, a method for predicting networktraffic bursts is disclosed. The method includes identifying, in data received by a networking device, a plurality of networktraffic bursts, each of the plurality of networktraffic bursts occurring at a respective one of plurality of bursttimes {t_{N}, t_{N1}, . . . , t_{0}}, N≥3. The method also includes determining a timeinterval τ_{n }of a next burst occurring at τ_{n }after bursttime t_{1 }by determining respective values of predicted timeinterval τ_{n}, a parameter ξ, and a parameter η. Timeinterval τ_{n}, parameter ξ, and parameter η minimize, to within a tolerance, a quantity (f_{k }(ξ, η, k)−(τ_{n}−t_{k})) for at least three values of a positive integer k≤N. Parameters ξ and η are, respectively, a real part and an imaginary part of a powerlaw exponent of a power law relating predicted timeinterval τ_{n }to any of the plurality of bursttimes. The method also includes determining, from a cumulative distribution function of a normal distribution of previouslyidentified networktraffic bursts associated with a previouslypredicted bursttime τ_{p}, a timeduration during which the networking device may reallocate bandwidth according to at least one of traffic type, a subnet mask, and IP address. Previouslypredicted bursttime τ_{p }differs from predicted timeinterval τ_{n }by less than a predetermined tolerance.
In a second aspect, networktraffic burst predictor is disclosed. The networktraffic burst predictor includes a processor communicatively coupled to both a networking device and a memory. The memory stores nontransitory computerreadable instructions that, when executed by the processor, control the processor to execute the method of the first aspect.
Embodiments disclosed herein employ a quantitative method for predicting the timing of bursts in communication network traffic, e.g. wireline communication network traffic or wireless communication network traffic. The predictions may be used to reallocate bandwidth in more optimal ways. For example, if the next burst is predicted to occur no earlier than the minutes from now with a certain probability, then these ten minutes of underutilized bandwidth may be reallocated to other uses.
In embodiments, a burst prediction model relies a power law distribution for the cumulative bytes that flow between bursts. Equation (1) is of simple powerlaw distribution:
Σbytes=C(τ_{n}−t)^{β}, (1)
where τ_{n }is a predicted timeinterval before the next burst, τ_{n}>t, and β is an index that, in embodiments, is positive and less than unity, such as ξ=0.84.
The flow of bytes per unit time is given by the derivative of the equation (1), equation (2), where α=β−1<0.
Flow=C(τ_{n}−t)^{α} (2)
In general, exponent a can be written as complex number α=ξ+iη, which enables equation (2) to be expressed as equation (3), where (τ_{n}−t)^{iη} is replaced by Re{cos(η ln(τ_{n}−t))+i sin(η ln(τ_{n}−t))}=cos(η ln(τ_{n}−t)), which ensures a noncomplex value for data rate.
Flow=C(τ_{n}−t)^{ξ} cos[η ln(τ_{n}−t)] (3)
Bursts by their very nature are local maxima of equation (3), such that they can be found by taking the first derivative of equation (3) and setting it equal to zero, as shown in equation (4).
Eliminating common factors and dividing by the cosine term yields equation (5).
ξ tan[η ln(τ_{n}−t_{k})±kπ]=ξ/η (5)
In equation (5), the kπ term denotes the kth maximum at time t_{k}. Applying the inverse tangent function to equation (5) and exponentiating both sides yields:
η ln(τ_{n}−t)±kπ=arctan(ξ/η) (6)
Solving equation (6) for τ_{n }and choosing the +kη yields equation (7), which relates the time to the next burst as measured from the kth previous burst:
τ_{n}=t_{k}+exp[η^{−1 }arctan(ξ/η)+kπ/η]. (7)
In general, the time of the burst at predicted burstinterval τ_{n }can be found given η and any two prior bursts p_{1 }and p_{2}, from the following equation:
τ_{n}=(t_{p}_{1}−t_{p}_{2}e^{(p}^{1}^{p}^{2}^{)π/η})/(1−e^{(p}^{1}^{p}^{2}^{)π/η}) (8)
Line 202 is a bestfit line to scatter plot 200 generated by applying N=6 measured burst times to equation (7), where ={m_{5}, m_{4}, m_{3}, m_{2}, m_{1}, m_{0}} denote the N measured burst times. In bursttime set , bursttime m_{k+1 }occurs before bursttime m_{k}. The measured burst times were applied to equation (7) as shown in equations (9a)(9e), hereinafter equations (9), to determine bestfit values of values of ξ and η, denoted herein as ξ_{fit }and η_{fit}, via a LevenbergMarquardt method. In embodiments, other curvefitting, minimization, and/or optimization methods may be used to determine ξ_{fit }and η_{fit}.
m_{0}=m_{1}+exp[η^{−1 }arctan(ξ/η)+π/η] (9a)
m_{0}=m_{2}+exp[η^{−1 }arctan(ξ/η)+2π/η] (9b)
m_{0}=m_{3}+exp[η^{−1 }arctan(ξ/η)+3π/η] (9c)
m_{0}=m_{4}+exp[η^{−1 }arctan(ξ/η)+4π/η] (9d)
m_{0}=m_{5}+exp[η^{−1 }arctan(ξ/η)+5π/η] (9e)
The values for ξ_{fit }and η_{fit }determined from equations (9), were applied again to equation (7) to predict nextburst estimates τ_{15}, as shown in equations (10a)(10e).
τ_{1}=m_{0}+exp[η_{fit}^{−1 }arctan(ξ_{fit}/η_{fit})+π/η_{fit}] (10a)
τ_{2}=m_{1}+exp[η_{fit}^{−1 }arctan(ξ_{fit}/η_{fit})+2π/η_{fit}] (10b)
τ_{3}=m_{2}+exp[η_{fit}^{−1 }arctan(ξ_{fit}/η_{fit})+3π/η_{fit}] (10c)
τ_{4}=m_{3}+exp[η_{fit}^{−1 }arctan(ξ_{fit}/η_{fit})+4π/η_{fit}] (10d)
τ_{5}=m_{4}+exp[η_{fit}^{−1 }arctan(ξ_{fit}/η_{fit})+5π/η_{fit}] (10e)
The predicted nextburst estimates τ_{15 }were averaged to yield a meanpredicted nextburst
The computations associated in equations (9) and (10) were repeated several times, each with a respective Nelement set of measured burst times, to generate scatter plot 200,
In the examples of
For a given interval of predicted bursts, the distributions of measured bursts in
The normal distribution of measured bursts with respect to predicted burstintervals τ_{n }enables use the cumulative distribution function (CDF) of the normal distribution to pick a QoS value. For example, in a use scenario, the predicted timeinterval until the next burst (predicted burstinterval τ_{n}) is close to a previouslypredicted interval τ_{p}. In embodiments, previouslypredicted interval τ_{p }is determined to be the one of P previouslypredicted intervals τ that is closest to predicted burstinterval τ_{n}. In embodiments, predicted burstinterval τ_{n }differs from a previouslypredicted interval τ_{p }by less than a predetermined difference δτ.
The normal distribution associated with previouslypredicted interval τ_{p }is characterized by a meanvalue μ_{p }and a standard deviation σ_{p}. In such a case, channel resources such as bandwidth may be freed for a time interval τ_{free }related to the CDF of the normal distribution:
CDF=½+½erf[(τ_{free}−μ_{p})/√{square root over (2)}σ_{p}]. (11)
In embodiments, meanvalue μ_{p }and a standard deviation σ_{p }are averages of normal distributions associated with a quantity Q<P previouslypredicted intervals τ that, among the P previously predicted intervals τ, are closest to predicted burstinterval τ_{n}. In embodiments, the Q previouslypredicted intervals represent a top quantile of the P previouslypredicted intervals in terms of their proximity to predicted burstinterval τ_{n}. The top quantile is, for example, a top decile or smaller group, such as a top two percent.
The value of CDF evaluated at time interval τ_{free }is the probability that the next burst will occur before predicted burstinterval τ_{n}. If a network device reallocates bandwidth during a nextburst interval τ_{free}, bursts occurring within nextburst interval τ_{free }decreases QoS for lack of sufficient bandwidth to accommodate the bursts. Quality of service QoS may be defined as the probability of having sufficient bandwidth during nextburst interval τ_{n}, or QoS=(1−CDF). When CDF equals zero and one, the probability of bandwidth being insufficient during nextburst interval τ_{free }is zero and one, respectively. Replacing CDF with QoS in equation (11) and solving for τ_{free }yields equation (12). That is, for a given τ_{n }and contracted CDF=(1−QoS) the resources are freed up for a time given by:
τ_{free}=√{square root over (2)}σ_{p}erf^{−1}(1−2QoS)+μ_{p}, (12)
where erf^{−1 }denotes the inverse error function.
In embodiments, the functional relationship between CDF and QoS differs from CDF=(1−QoS). For example, the qualityofservice metric may be a decreasing function of the cumulative distribution function.
Network device 520 is communicatively connected to network nodes 530(1M_{0}) via a plurality of communication channels 535(1M_{5}). Network device 520 is communicatively connected to network nodes 550(1N_{0}) via a plurality of network channels 545(1N_{5}). Traffic on any one of communication channels 535 and 555 may include network traffic bursts, of which networktraffic bursts 110 are an example. Traffic on any of communication channels 535 and 555 may be en route either to or from any one of network nodes 530 and 550. In embodiments, integer M_{5 }may be less than or equal to integer M_{0}, and integer N_{5 }is less than or equal to integer N_{0}.
In some embodiments, network 500 includes part or all of a wireline communication network and/or a wireless communication network. Some examples of possible wireline communication networks include networks operating according to one or more of a data over cable services interface specification (DOCSIS) protocols, digital subscriber line (DSL) protocols, ethernet passive optical network (EPON) protocols, gigabit passive optical network (GPON) protocols, and radio frequency over glass (RFOG) protocols. Some examples of possible wireless networks include networks operating according to one or more of long term evolution (LTE) protocols, fifth generation (5G) new radio (NR) protocols, sixth generation (6G) protocols, WiFi protocols, microwave communication protocols, and Satellite communication protocols.
Burst predictor 510 includes a memory 514 communicatively coupled to a processor 512. Memory 514 may be transitory and/or nontransitory and may include one or both of volatile memory (e.g., SRAM, DRAM, computational RAM, other volatile memory, or any combination thereof) and nonvolatile memory (e.g., FLASH, ROM, magnetic media, optical media, other nonvolatile memory, or any combination thereof). Part or all of memory 514 may be integrated into processor 512. Memory 514 includes machinereadable instructions. Processor 512 is adapted to execute the machinereadable instructions to perform functions of burst predictor 510 described herein.
Step 610 includes identifying, in data received by a networking device, a plurality of networktraffic bursts, each of the plurality of networktraffic bursts occurring at a respective one of plurality of bursttimes {t_{N}, t_{N1}, . . . , t_{0}}, N≥3. In an example of step 610, one of network device 520 and burst predictor 510 detects networktraffic bursts in network channel 535(1) of network 500.
Step 620 includes determining a timeinterval τ_{n }of a next burst occurring at τ_{n }after bursttime t_{1 }by determining respective values of predicted timeinterval τ_{n}, a parameter ξ, and a parameter η. Timeinterval τ_{n}, parameter ξ, and parameter η minimize, to within a tolerance, a quantity (f_{k }(ξ, η, k)−(τ_{n}−t_{k})) for at least three values of a positive integer k≤N. Parameters ξ and η are, respectively, a real part and an imaginary part of a powerlaw exponent of a power law relating predicted timeinterval τ_{n }to any of the plurality of bursttimes. In an example of step 620, burst predictor 510 determines meanpredicted nextburst
In embodiments, step 620 includes at least one of steps 622 and 624. Step 622 includes determining values ξ_{min }and η_{min }of parameters ξ and η as those that minimize, within a predetermined tolerance a combination of (f_{k }(ξ, η, k)−(t_{n}−t_{k})) for k=1, 2, . . . , N. Step 624 includes determining τ_{n }as an average of burst intervals τ_{k}=t_{k}+f_{k }(ξ_{min}, η_{min}, k), for k=1, 2, . . . , N. In an example of step 622, burst predictor 510 determines parameters ξ and η that minimize equations (9) to within a predetermined tolerance. In an example of step 620, burst predictor 624 determines meanpredicted nextburst
Step 630 includes determining, from a cumulative distribution function of a normal distribution of previouslyidentified networktraffic bursts associated with a previouslypredicted bursttime τ_{p}, a timeduration during which the networking device may reallocate bandwidth according to at least one of traffic type, a subnet mask, and IP address. Previouslypredicted bursttime τ_{p }differs from predicted timeinterval τ_{n }by less than a predetermined tolerance. In an example of step 630, burst predictor 510 determines nextburst interval τ_{free }per equations (11) and (12).
In embodiments, step 630 includes at least one of steps 632, 634, and 636. Step 632 includes determining the timeduration from a mean bursttime μ_{p }and a standard deviation σ_{p }of the normal distribution. In an example of step 632, burst predictor 510 determines nextburst interval τ_{free }in part from equations (11) and (12), which include mean bursttime μ_{p }and standard deviation σ_{p}.
Step 634 includes determining the timeduration as √{square root over (2)}σ_{p }erf^{−1}(1−2QoS)+μ_{p}, where QoS is a predetermined metric related to a probability of having sufficient bandwidth during the timeduration. In an example of step 634, burst predictor 510 determines nextburst interval τ_{free }using equation (12).
Step 636 includes determining the mean bursttime μ_{p }and the standard deviation σ_{p }by curvefitting the previouslyidentified networktraffic bursts. In a first example of step 636, burst predictor 510 fits normal distribution 212 to measured traffic bursts occurring in timeinterval 210,
Step 640 includes reallocating bandwidth during the timeduration and according to at least one of traffic type, a subnet mask, and IP address during the timeduration. In an example of step 640, burst predictor 510 reallocated bandwidth from communication channel 535(1) to one or more communication channels 535(2M_{5}) during nextburst interval τ_{free}.
Changes may be made in the above methods and systems without departing from the scope hereof. It should thus be noted that the matter contained in the above description or shown in the accompanying drawings should be interpreted as illustrative and not in a limiting sense. Herein, and unless otherwise indicated, the adjective “exemplary” means serving as an example, instance, or illustration. The following claims are intended to cover all generic and specific features described herein, as well as all statements of the scope of the present method and system, which, as a matter of language, might be said to fall therebetween.