|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectunikl.disco.nc.Curve
public class Curve
Class representing a piecewise linear curve, defined on [0,inf).
The curve is stored as an array of LinearSegment
objects. Each of these objects defines a linear piece of the
curve from one inflection point up to, but not including, the
next. It is possible to define discontinuities by defining two
subsequent LinearSegment
instances which start at
the same inflection point. In this case, the second segment
needs to have leftopen
set to true
to
indicate that the inflection point is excluded from the second
segment.
All arithmetic operations on a curve return a new instance of class
Curve
.
Field Summary | |
---|---|
static boolean |
create_labels
|
static Curve |
NULL_CURVE
|
static Curve |
ZERO_DELAY_BURST_CURVE
|
Constructor Summary | |
---|---|
Curve(double[] ip_xs,
double[] ip_ms)
Creates a Curve instance with inflection points at
the x-coordinates ip_xs and with slopes defined
by ip_ms . |
|
Curve(double[] ip_xs,
double[] ip_ys,
double[] ip_ms,
int compute_y_start)
Creates a Curve instance with inflection points at
the x-coordinates ip_xs and with slopes defined
by ip_ms . |
Method Summary | |
---|---|
Curve |
add(Curve other)
Returns a curve that is the sum of this curve and the given curve. |
Curve |
add(double dy)
Returns a copy of this curve shifted vertically by dy . |
void |
addSegment(int pos,
LinearSegment s)
Adds a LinearSegment at the location pos
of the curve. |
void |
addSegment(LinearSegment s)
Adds a LinearSegment to the end of the curve. |
void |
approximateAtSegment(int i)
Approximates a (concave) arrival curve by removing the specified segment. |
int |
approximateSegments(double dy)
Approximates arrival curve by removing all segments whose projection onto the y-axis has a height smaller than dy . |
void |
beautify()
Removes unnecessary segments. |
Curve |
boundAtXAxis()
Returns a copy of this curve bounded at the x-axis. |
static Curve |
computeFIFOServiceCurve(Curve alpha,
Curve beta)
Computes the effetive FIFO service curve for a server with the service curve beta experiencing cross-traffic with arrival curve alpha . |
static java.util.ArrayList |
computeInflectionPointsX(Curve c1,
Curve c2)
Returns an ArrayList instance of those x-coordinates
at which either c1 or c2 or both have an inflection point. |
static java.util.ArrayList |
computeInflectionPointsY(Curve c1,
Curve c2)
Returns an ArrayList instance of those y-coordinates
at which either c1 or c2 or both have an inflection point. |
void |
computeYs(int start)
Computes the y-coordinates of inflection points starting with inflection point start . |
Curve |
convolveAlmostConcave(Curve other)
Returns the convolution of this curve, which must be (almost) concave, and the given curve, which must also be (almost) concave. |
Curve |
convolveConvex(Curve other)
Returns the convolution of this curve, which must be convex, and the given curve, which must also be convex. |
Curve |
copy()
Returns a copy of this instance. |
static Curve |
createBurstDelay(double t)
Creates a burst delay curve. |
static Curve |
createFromTokenBuckets(java.util.List token_buckets)
Creates a new curve from a list of token bucket curves. |
static Curve |
createHorizontal(double y)
Creates a horizontal curve. |
static Curve |
createRateLatency(double t,
double r)
Creates a new rate latency curve. |
static Curve |
createTokenBucket(double b,
double r)
Creates a new token bucket curve. |
Curve |
deconvolve(Curve other)
Returns the deconvolution of this curve, which must be (almost) concave, and the given curve, which must convex. |
void |
dump()
Prints the string representation of this curve to stdout. |
double |
f_inv(double y)
Returns the smallest x value at which the function value is equal to y . |
double |
f_inv(double y,
boolean rightmost)
Returns the x value at which the function value is equal to y . |
double |
f(double x)
Returns the function value at x-coordinate x , if
x>=0 , and NaN if not. |
double |
fLimitRight(double x)
Returns the limit to the right of the function value at x-coordinate x , if x>=0 , and
NaN if not. |
java.lang.String |
getAlias()
Returns a string with a user-defined alias name for the function. |
static double |
getBacklogBound(Curve alpha,
Curve beta)
Returns the backlog bound of the given two curves. |
static double |
getDelayBound(Curve alpha,
Curve beta)
Returns the delay bound of the given two curves. |
double |
getGradientAt(double x)
Returns the curve's gradient at x-coordinate x , if
x>=0 , and NaN if not. |
double |
getGradientLimitRight(double x)
Returns the gradient to the right of the function value at x-coordinate x , if x>=0 , and
NaN if not. |
double |
getHighestRate()
Returns the highest rate (the steepest gradient of any segment). |
static double |
getHorizontalDeviation(Curve c1,
Curve c2)
Returns the horizontal deviation between the given two curves. |
double |
getIPX(int i)
Returns the x-coordinate of inflection point i . |
double |
getIPY(int i)
Returns the y-coordinate of inflection point i . |
java.lang.String |
getLabel()
Returns a string with an automatically created label for the function. |
double |
getLatency()
Returns the x-coordinate of the inflection point after which the function values are greater than zero. |
double |
getMaxX()
Returns the largest x for which the curve is defined. |
double |
getMinX()
Returns the smallest x for which the curve is defined. |
Curve |
getRLComponent(int i)
Returns the i th rate latency curve that this curve can be
decomposed into. |
int |
getRLComponentCount()
Returns the number of rate latency curves the curve can be decomposed into. |
java.util.List |
getRLComponents()
Returns a list of rate latency curves that this curve can be decomposed into. |
int |
getSegmentCount()
Returns the number of segments in this curve. |
int |
getSegmentDefining(double x)
Returns the number of the segment that defines the function value at x-coordinate x . |
int |
getSegmentFirstAtValue(double y)
Returns the first segment at which the function reaches the value y . |
int |
getSegmentLimitRight(double x)
Returns the number of the segment that defines the value of the function when computing the limit to the right of the function at x-coordinate x . |
double |
getSustainedRate()
Returns the sustained rate (the gradient of the last segment). |
double |
getTBBurst()
Returns the burstiness of this token bucket curve. |
Curve |
getTBComponent(int i)
Returns the i th token bucket curve that this curve can be
decomposed into. |
int |
getTBComponentCount()
Returns the number of token buckets the curve can be decomposed into. |
java.util.List |
getTBComponents()
Returns a list of token bucket curves that this curve can be decomposed into. |
static double |
getVerticalDeviation(Curve c1,
Curve c2)
Returns the vertical deviation between the given two curves. |
java.util.List |
getYIntervals()
Returns a list containing each segment's height when projected onto the y-axis. |
boolean |
isAlmostConcave()
Tests whether the curve is almost concave, i.e. it is concave once its function value is larger than 0. |
boolean |
isArrivalCurve()
Tests whether the curve is wide-sense increasing and satisfies f(0)=0. |
boolean |
isBurstDelay()
Returns whether the current curve is a burst delay curve. |
boolean |
isConcave()
Tests whether the curve is concave. |
boolean |
isConcaveIn(double a,
double b)
Tests whether the curve is concave in [a,b]. |
boolean |
isConvex()
Tests whether the curve is convex. |
boolean |
isConvexIn(double a,
double b)
Tests whether the curve is convex in [a,b]. |
boolean |
isDiscontinuity(int i)
Returns whether the inflection point is a (real or unreal) discontinuity. |
boolean |
isLeftopen(int i)
Returns whether the inflection point i is excluded
from the segment or not. |
boolean |
isRealDiscontinuity(int i)
Returns whether the inflection point is a real discontinuity, i.e. the y0 of the leftopen segment differs from the previous one. |
boolean |
isUnrealDiscontinuity(int i)
Returns whether the inflection point is an unreal discontinuity, i.e. the y0 of the leftopen segment is coincident with the y0 of the previous segment and therefore the unreal discontinuity may safely be removed. |
boolean |
isWideSenseIncreasing()
Tests whether the curve is wide-sense increasing. |
Curve |
makeArrivalCurve()
Returns a copy of this curve ensuring that f(0)=0. |
void |
makeTBRightContinuous()
Makes the token bucket curve right-continuous. |
void |
markDiscontinuities()
Marks discontinuities (subsequent segments having the same x-coordinate) by setting leftopen of the second segment. |
Curve |
max(Curve other)
Returns a curve that is the maximum of this curve and the given curve. |
Curve |
min(Curve other)
Returns a curve that is the minimum of this curve and the given curve. |
Curve |
removeLatency()
Returns a copy of this curve with latency removed, i.e. shifted left by the latency. |
void |
removeSegment(int pos)
Removes the segment at position pos . |
void |
setAlias(java.lang.String alias)
Allows the user to set an alias name for the function which overrides the automatically created label. |
static void |
setCreateLabels(boolean create_labels)
Whether to auto-create labels for curves. |
void |
setSustainedRate(double r)
Sets the sustained rate (the gradient of the last segment). |
void |
setTBBurst(double b)
Sets the burstiness of this token bucket curve. |
Curve |
shiftLeftClipping(double dx)
Returns a copy of this curve that is shifted to the left by dx ,
i.e. g(x) = f(x+dx). |
Curve |
shiftRight(double dx)
Returns a copy of this curve that is shifted to the right by dx ,
i.e. g(x) = f(x-dx). |
Curve |
sub(Curve other)
Returns a curve that is the difference between this curve and the given curve. |
java.lang.String |
toString()
Returns a string representation of this curve. |
void |
undoMakeTBRightContinuous()
Undoes the makeTBRightContinuous() operation. |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait |
Field Detail |
---|
public static final Curve NULL_CURVE
public static final Curve ZERO_DELAY_BURST_CURVE
public static boolean create_labels
Constructor Detail |
---|
public Curve(double[] ip_xs, double[] ip_ms)
Curve
instance with inflection points at
the x-coordinates ip_xs
and with slopes defined
by ip_ms
. The y-coordinates are computed automatically.
ip_xs
- ip_ms
- public Curve(double[] ip_xs, double[] ip_ys, double[] ip_ms, int compute_y_start)
Curve
instance with inflection points at
the x-coordinates ip_xs
and with slopes defined
by ip_ms
. This constructor accepts an array of
y-coordinates so that discontinuities can be created. The
parameter compute_y_start
indicates from which
inflection point (starting with 0), the y-coordinate is again
computed automatically. Note that all arrays need to have the
same length.
ip_xs
- ip_ms
- Method Detail |
---|
public static Curve createHorizontal(double y)
y
- the y-intercept of the curve
Curve
instancepublic static Curve createBurstDelay(double t)
t
- the delay, which must be >= 0.0
Curve
instancepublic static Curve createTokenBucket(double b, double r)
b
- the burstinessr
- the rate
Curve
instancepublic static Curve createRateLatency(double t, double r)
t
- the latencyr
- the rate
Curve
instancepublic static Curve createFromTokenBuckets(java.util.List token_buckets)
token_buckets
- a list of token bucket curves
Curve
instancepublic Curve copy()
public static void setCreateLabels(boolean create_labels)
create_labels
- public java.lang.String getLabel()
Function
null
.
getLabel
in interface Function
public void setAlias(java.lang.String alias)
Function
setAlias
in interface Function
alias
- the alias namepublic java.lang.String getAlias()
Function
getAlias
in interface Function
public int getSegmentCount()
getSegmentCount
in interface PWLFunction
public double getIPX(int i)
i
.
getIPX
in interface PWLFunction
i
- the index of the IP.
public double getIPY(int i)
i
.
getIPY
in interface PWLFunction
i
- the index of the IP.
public double getSustainedRate()
public double getHighestRate()
public void setSustainedRate(double r)
r
is larger (smaller) than
the gradient of the 2nd-to-last segment to keep the curve convex (concave).
r
- the new sustained ratepublic boolean isLeftopen(int i)
i
is excluded
from the segment or not.
isLeftopen
in interface PWLFunction
i
- the index of the IP.
true
if the IP is excluded, false
if not.public boolean isDiscontinuity(int i)
i
- the index of the IP
true
if the IP is a discontinuity, false
if not.public boolean isRealDiscontinuity(int i)
i
- the index of the IP
true
if the IP is a real discontinuity, false
if not.public boolean isUnrealDiscontinuity(int i)
i
- the index of the IP
true
if the IP is an unreal discontinuity, false
if not.public boolean isBurstDelay()
true
if the curve is burst delay, false
otherwisepublic void addSegment(LinearSegment s)
LinearSegment
to the end of the curve.
s
- the segment to be added.public void addSegment(int pos, LinearSegment s)
LinearSegment
at the location pos
of the curve.
pos
- the index into the segment array to add the new segment.s
- the segment to be added.public void removeSegment(int pos)
pos
.
pos
- the index of the segment to be removed.public void markDiscontinuities()
leftopen
of the second segment.
public void computeYs(int start)
start
.
start
- the IP at which to start computing y-coordinates.public int getTBComponentCount()
public final java.util.List getTBComponents()
public Curve getTBComponent(int i)
i
th token bucket curve that this curve can be
decomposed into.
i
- the number of the token bucket
public double getTBBurst()
public void setTBBurst(double b)
b
- the burstinesspublic void makeTBRightContinuous()
public void undoMakeTBRightContinuous()
public int getRLComponentCount()
public final java.util.List getRLComponents()
public Curve getRLComponent(int i)
i
th rate latency curve that this curve can be
decomposed into.
i
- the number of the rate latency curve
public void beautify()
public int getSegmentDefining(double x)
x
. The
number of the segment is usually the same as the one
returned by getSegmentLimitRight(x)
, except for
if a segment starts at x
and is left-open.
In this case the function returns the previous segment,
rather than the current segment, as the previous segment
defines x
.
x
- the x-coordinate
public double f(double x)
x
, if
x>=0
, and NaN
if not.
f
in interface Function
x
- the x-coordinate
public double getGradientAt(double x)
x
, if
x>=0
, and NaN
if not. Note that the
gradient returned at discontinuities is 0.0
, the
gradient returned at an inflection point is the gradient of the
linear segment right of the inflection point, but only if the
segment is not left-open.
getGradientAt
in interface Function
x
- the x-coordinate
public int getSegmentLimitRight(double x)
x
. The
number of the segment is usually the same as the one
returned by getSegmentDefining(x)
, except for
if a segment starts at x
and is left-open.
In this case the function returns the current segment,
rather than the previous segment.
x
- the x-coordinate
public double fLimitRight(double x)
x
, if x>=0
, and
NaN
if not.
x
- the x-coordinate
public double getGradientLimitRight(double x)
x
, if x>=0
, and
NaN
if not.
x
- the x-coordinate
public int getSegmentFirstAtValue(double y)
y
. It returns -1 if the curve never
reaches this value.
y
- the y-coordinate
public double f_inv(double y)
y
.
y
- the y-coordinate
public double f_inv(double y, boolean rightmost)
y
. If rightmost
is
true
, returns the rightmost x-coordinate,
otherwise the leftmost coordinate.
y
- the y-coordinate
public double getMinX()
getMinX
in interface Function
public double getMaxX()
getMaxX
in interface Function
public boolean isWideSenseIncreasing()
public boolean isArrivalCurve()
public boolean isConvex()
public boolean isConvexIn(double a, double b)
a
- the lower bound of the test interval.b
- the upper bound of the test interval.
public boolean isConcave()
public boolean isConcaveIn(double a, double b)
a
- the lower bound of the test interval.b
- the upper bound of the test interval.
public boolean isAlmostConcave()
public Curve add(Curve other)
other
- the given curve.
public Curve sub(Curve other)
other
- the given curve.
public Curve min(Curve other)
other
- the given curve.
public Curve max(Curve other)
other
- the given curve.
public Curve shiftRight(double dx)
dx
,
i.e. g(x) = f(x-dx).
dx
- the offset to shift the curve.
public Curve shiftLeftClipping(double dx)
dx
,
i.e. g(x) = f(x+dx). Note that the new curve is clipped at the y-axis so
that in most cases c.shiftLeftClipping(dx).shiftRight(dx) != c
!
dx
- the offset to shift the curve.
public Curve removeLatency()
public Curve boundAtXAxis()
public Curve add(double dy)
dy
.
dy
- the offset to shift the curve.
public double getLatency()
public Curve convolveAlmostConcave(Curve other)
other
- the curve to convolve with.
public Curve convolveConvex(Curve other)
other
- the curve to convolve with.
public Curve deconvolve(Curve other)
other
- the curve to convolve with.
public Curve makeArrivalCurve()
public static Curve computeFIFOServiceCurve(Curve alpha, Curve beta)
beta
experiencing cross-traffic with arrival curve alpha
.
alpha
- arrival curve of cross-trafficbeta
- server's service curve
public static double getBacklogBound(Curve alpha, Curve beta)
alpha
- the arrival curve.beta
- the service curve.
public static double getVerticalDeviation(Curve c1, Curve c2)
c1
- the first curve.c2
- the second curve.
public static double getDelayBound(Curve alpha, Curve beta)
alpha
- the arrival curve.beta
- the service curve.
public static double getHorizontalDeviation(Curve c1, Curve c2)
c1
- the first curve.c2
- the second curve.
public static java.util.ArrayList computeInflectionPointsX(Curve c1, Curve c2)
ArrayList
instance of those x-coordinates
at which either c1 or c2 or both have an inflection point. There
will be multiple occurences of an x-coordinate, if at least one
curve has a discontinuity at that x-coordinate.
c1
- the first curve.c2
- the second curve.
ArrayList
of Double
objects
containing the x-coordinates of the respective inflection point.public static java.util.ArrayList computeInflectionPointsY(Curve c1, Curve c2)
ArrayList
instance of those y-coordinates
at which either c1 or c2 or both have an inflection point.
c1
- the first curve.c2
- the second curve.
ArrayList
of Double
objects
containing the x-coordinates of the respective inflection point.public java.util.List getYIntervals()
public int approximateSegments(double dy)
dy
. Returns the number of
removed segments.
dy
- the height below which segments are removed
public void approximateAtSegment(int i)
i
- the index of the segment to removepublic java.lang.String toString()
toString
in class java.lang.Object
public void dump()
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |