|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectunikl.disco.nc.NetworkAnalyser
public class NetworkAnalyser
Class containing various methods to analyse a network. It operates on a server graph (i.e. vertices representing servers, edges representing dependencies between servers) which must not contain cyclic dependencies.
Field Summary | |
---|---|
protected java.util.List |
flows
A list of all flows in the network |
protected int |
max_rec_depth_for_pmoo
How many levels of recursion the tighter computePMOOOutputBound() is used
rather than standard computeOutputBound() . |
protected int |
rec_depth
The current recursion level |
protected edu.uci.ics.jung.graph.DirectedGraph |
server_graph
The server model graph to analyse |
protected double |
token_bucket_count_target
The targeted number of TBs per flow when reducing complexity |
protected boolean |
use_arrival_curve_approximation
Whether to use arrival curve approximation |
protected boolean |
use_extra_gamma
Whether to constrain the output bound further through convolution with the maximum service curve |
protected boolean |
use_fifo_service
Whether to use FIFO service instead of blind multiplexing |
protected boolean |
use_flow_prolongation
Whether to prolong flows to reduce complexity |
protected boolean |
use_gamma
Whether to use maximum service curves in output bound computation |
Constructor Summary | |
---|---|
NetworkAnalyser(edu.uci.ics.jung.graph.DirectedGraph server_graph)
|
Method Summary | |
---|---|
void |
addFlow(Flow flow)
Adds a flow to the network analyser. |
protected void |
approximateArrivalCurves(java.util.Set all_interfering_flows,
java.util.Map flow_bound_map)
Approximates arrival curves by ones with fewer number of segments. |
void |
autoAdjustServerRate(edu.uci.ics.jung.graph.Vertex server,
double target_link_utilization)
Adjusts the rates of a given server's service curves so that the utilization of the server is below or equal to target_link_utilization . |
Curve |
computeOutputBound(edu.uci.ics.jung.graph.Vertex server,
java.util.Set outgoing_flows)
Returns the output bound for a set of outgoing_flows from
the given server . |
protected Curve |
computePartialPMOOServiceCurve(Curve[] service_curves,
java.util.Set all_interfering_flows,
java.util.List joining_flow_sets,
java.util.Map flow_egress_map,
java.util.Map flow_bound_map,
java.util.Map flow_tb_iter_map,
int[] server_rl_iters)
Calculates the partial PMOO service curve for the given flow set by combining all servers having an outgoing edge contained in the given edge-path. |
protected Curve |
computePMOOOutputBound(edu.uci.ics.jung.graph.Vertex server,
java.util.Set flows_of_interest)
Computes the PMOO output bound for a set of flows_of_interest . |
protected Curve |
computePMOOServiceCurve(java.util.List path,
java.util.Set all_interfering_flows,
java.util.List joining_flow_sets,
java.util.Map flow_egress_map,
java.util.Map flow_bound_map,
int rec_depth)
Concatenates the service curves along the given path path according to
the PMOO approach and returns the result. |
Curve |
convolveMaxServiceCurves(java.util.List path)
Returns the convolution of the maximum service curves of all servers on the given edge path path . |
Curve |
convolveServiceCurves(java.util.List path)
Returns the convolution of the service curves of all servers on the given edge path path . |
protected edu.uci.ics.jung.graph.Vertex |
findSplittingPoint(edu.uci.ics.jung.graph.Vertex server,
java.util.Set flows_of_interest)
Returns the server at which the flows in flows_of_interest first
all meet each other (when viewed from the source). |
java.util.Set |
getAllIncomingFlows(edu.uci.ics.jung.graph.Vertex server)
Returns the set of all flows that enter server from one
of its predecessors. |
java.util.Map |
getCharnyBacklogBounds()
Computes the Charny backlog bound for each server. |
double |
getCharnyDelayBound()
Returns the Charny delay bound if it exists, otherwise returns Double.POSITIVE_INFINITY . |
java.util.List |
getFlows()
Returns all flows registered with the network analyser. |
java.util.Set |
getFlowSet(edu.uci.ics.jung.graph.DirectedEdge e)
Returns a set containing all flows traversing the given edge e . |
double |
getHighestServerUtilization()
Returns the highest server utilization in the network. |
java.util.Set |
getIncomingFlows(edu.uci.ics.jung.graph.Vertex predecessor,
edu.uci.ics.jung.graph.Vertex server)
Returns a set containing all flows traversing the edge from predecessor to server . |
int |
getMaxFlowLength(java.util.List flows)
Returns the length of the longest flow in the given list of flows. |
int |
getMaxRecursionDepthForPMOO()
|
Curve |
getMaxServiceCurve(edu.uci.ics.jung.graph.Vertex server)
Returns the maximum service curve of a given server or a
burst-delay-curve with delay 0.0 if no maximum service curve is defined
for the server. |
double |
getMaxUtilizationForCharnyBound()
Returns the maximum server utilization for which the Charny bound exist. |
protected Curve |
getPMOOServiceCurve(java.util.List path,
java.util.Set flows_of_interest)
Returns the PMOO service curve for a set of flows_of_interest . |
edu.uci.ics.jung.graph.Vertex |
getPredecessor(edu.uci.ics.jung.graph.Vertex server,
Flow f)
Returns the predecessor server from which a given server receives
the flow f . |
Curve |
getServiceCurve(edu.uci.ics.jung.graph.Vertex server)
Returns the (minimum) service curve of a given server |
Curve |
getSourceFlow(edu.uci.ics.jung.graph.Vertex source,
java.util.Set outgoing_flows)
Returns an aggregate arrival curve for all flows originating in source and contained in the set outgoing_flows . |
double |
getTokenBucketCountTarget()
|
protected boolean |
isFreeProlongation(Flow short_flow,
Flow long_flow,
java.util.List server_residual_rates,
java.util.List passing_flow_sets,
java.util.Map flow_min_residual_rates,
java.util.Map flow_egress_map,
java.util.Map flow_bound_map)
Tests whether the prolongation of a flow is for free, i.e. it does not change the output bound. |
boolean |
isUseArrivalCurveApproximation()
|
Curve |
performFairQueueingAnalysis(Flow flow_of_interest)
Performs a fair queueing analysis and returns the end-to-end service curve for a the given flow_of_interest . |
Curve |
performPMOOAnalysis(Flow flow_of_interest)
Performs a pay-multiplexing-only-once (PMOO) analysis for the flow_of_interest and returns the end-to-end service curve. |
Curve |
performSeparatedFlowAnalysis(Flow flow_of_interest)
Performs a separated flow analysis for the flow_of_interest and returns
the end-to-end service curve. |
double |
performTotalFlowAnalysis(Flow flow_of_interest,
java.util.Map server_to_backlog_bound_map)
Performs a total flow analysis for the flow_of_interest and returns
the end-to-end delay bound. |
protected void |
prolongFlows(java.util.List path,
java.util.Set all_interfering_flows,
java.util.List joining_flow_sets,
java.util.Map flow_egress_map,
java.util.Map flow_bound_map)
Tries to prolong flows having the same ingress but different egress points so that they may be aggregated. |
void |
removeFlow(Flow flow)
Removes a flow from the network analyser. |
void |
setMaxRecursionDepthForPMOO(int max_rec_depth_for_pmoo)
|
void |
setMaxServiceCurve(java.util.Set servers,
Curve prototype_max_service_curve)
Sets the maximum service curve for the specified set of servers to a copy of the specified prototype_max_service_curve |
void |
setMaxServiceCurve(edu.uci.ics.jung.graph.Vertex server,
Curve max_service_curve)
Sets the maximum service curve for the specified server. |
void |
setServiceCurve(java.util.Set servers,
Curve prototype_service_curve)
Sets the service curve for the specified set of servers to a copy of the specified prototype_service_curve |
void |
setServiceCurve(edu.uci.ics.jung.graph.Vertex server,
Curve service_curve)
Sets the service curve for the specified server. |
void |
setTokenBucketCountTarget(double token_bucket_count_target)
|
void |
setUseArrivalCurveApproximation(boolean use_arrival_curve_approximation)
|
void |
setUseExtraGamma(boolean use_extra_gamma)
|
void |
setUseFifoService(boolean use_fifo_service)
|
void |
setUseFlowProlongation(boolean use_flow_prolongation)
|
void |
setUseGamma(boolean use_gamma)
|
boolean |
useExtraGamma()
|
boolean |
useFifoService()
|
boolean |
useFlowProlongation()
|
boolean |
useGamma()
|
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Field Detail |
---|
protected boolean use_fifo_service
protected boolean use_gamma
protected boolean use_extra_gamma
protected int max_rec_depth_for_pmoo
computePMOOOutputBound()
is used
rather than standard computeOutputBound()
.
protected boolean use_arrival_curve_approximation
protected double token_bucket_count_target
protected boolean use_flow_prolongation
protected edu.uci.ics.jung.graph.DirectedGraph server_graph
protected int rec_depth
protected java.util.List flows
Constructor Detail |
---|
public NetworkAnalyser(edu.uci.ics.jung.graph.DirectedGraph server_graph)
server_graph
- the (server) graph to analyseMethod Detail |
---|
public boolean useFifoService()
public void setUseFifoService(boolean use_fifo_service)
public boolean useGamma()
public void setUseGamma(boolean use_gamma)
public boolean useExtraGamma()
public void setUseExtraGamma(boolean use_extra_gamma)
public int getMaxRecursionDepthForPMOO()
public void setMaxRecursionDepthForPMOO(int max_rec_depth_for_pmoo)
public boolean useFlowProlongation()
public void setUseFlowProlongation(boolean use_flow_prolongation)
public boolean isUseArrivalCurveApproximation()
public void setUseArrivalCurveApproximation(boolean use_arrival_curve_approximation)
public double getTokenBucketCountTarget()
public void setTokenBucketCountTarget(double token_bucket_count_target)
public Curve getServiceCurve(edu.uci.ics.jung.graph.Vertex server)
server or
a null-curve if no service curve is defined for the server.
- Parameters:
server
-
- Returns:
- the service curve
public void setServiceCurve(edu.uci.ics.jung.graph.Vertex server, Curve service_curve)
server
- the serverservice_curve
- the service curvepublic void setServiceCurve(java.util.Set servers, Curve prototype_service_curve)
prototype_service_curve
servers
- the set of servers whose service curve shall be setprototype_service_curve
- the prototype service curvepublic Curve getMaxServiceCurve(edu.uci.ics.jung.graph.Vertex server)
server
or a
burst-delay-curve with delay 0.0 if no maximum service curve is defined
for the server.
server
-
public void setMaxServiceCurve(edu.uci.ics.jung.graph.Vertex server, Curve max_service_curve)
server
- the servermax_service_curve
- the service curvepublic void setMaxServiceCurve(java.util.Set servers, Curve prototype_max_service_curve)
prototype_max_service_curve
servers
- the set of servers whose maximum service curve shall be setprototype_max_service_curve
- the prototype maximum service curvepublic void autoAdjustServerRate(edu.uci.ics.jung.graph.Vertex server, double target_link_utilization)
target_link_utilization
. target_link_utilization
, the mimimum service rate is increased
until the target utilization is reached. Furthermore, the rate of the maximum
service curve is increased as well, so that the ratio between maximum rate
and minimum rate is preserved.
server
- target_link_utilization
- the maximum link utilization for the serverpublic Curve convolveServiceCurves(java.util.List path)
path
.
path
- an edge path
public Curve convolveMaxServiceCurves(java.util.List path)
path
.
path
- an edge path
public void addFlow(Flow flow)
flow
- the flow to be addedpublic void removeFlow(Flow flow)
flow
- the flow to be removedpublic java.util.List getFlows()
public java.util.Set getFlowSet(edu.uci.ics.jung.graph.DirectedEdge e)
e
.
e
- the traversed edge
public java.util.Set getIncomingFlows(edu.uci.ics.jung.graph.Vertex predecessor, edu.uci.ics.jung.graph.Vertex server)
predecessor
to server
.
predecessor
- server
-
public java.util.Set getAllIncomingFlows(edu.uci.ics.jung.graph.Vertex server)
server
from one
of its predecessors.
server
-
public Curve getSourceFlow(edu.uci.ics.jung.graph.Vertex source, java.util.Set outgoing_flows)
source
and contained in the set outgoing_flows
.
source
- the source of all flows to be aggregatedoutgoing_flows
- the set of all flows to be aggregated
public edu.uci.ics.jung.graph.Vertex getPredecessor(edu.uci.ics.jung.graph.Vertex server, Flow f)
server
receives
the flow f
.
server
- the receiving serverf
- the incoming flow
public int getMaxFlowLength(java.util.List flows)
flows
- a list of flows
public double getMaxUtilizationForCharnyBound()
public double getCharnyDelayBound()
Double.POSITIVE_INFINITY
.
getMaxUtilizationForCharnyBound()
public java.util.Map getCharnyBacklogBounds()
Vertex
instances)
as keys and their corresponding backlog bound (Double
instances)
as values. If the bound does not exist, returns an empty map.
getMaxUtilizationForCharnyBound()
public double getHighestServerUtilization()
getMaxUtilizationForCharnyBound()
.
getMaxUtilizationForCharnyBound()
public Curve computeOutputBound(edu.uci.ics.jung.graph.Vertex server, java.util.Set outgoing_flows)
outgoing_flows
from
the given server
.outgoing_flows
) and all cross flows (incoming flows not
contained in outgoing_flows
).setUseFIFOService(true)
on
the analyser instance before computing any bounds.setUseGamma(true)
on the analyser instance to globally activate the
additional use of the maximum service curve for output bound computation.
Finally, by invoking setUseExtraGamma(true)
it is possible to convolve
the obtained output bound once more with the maximum service curve whose latency
has been removed before returning the result.
server
- the server at which the output bound is computedoutgoing_flows
- set of flows for which the output bound is computed
Curve
instance containing the output boundsetUseFifoService(boolean)
,
setUseGamma(boolean)
,
setUseExtraGamma(boolean)
public Curve performFairQueueingAnalysis(Flow flow_of_interest)
flow_of_interest
.
flow_of_interest
- the flow for which the end-to-end service curve is computed
public double performTotalFlowAnalysis(Flow flow_of_interest, java.util.Map server_to_backlog_bound_map)
flow_of_interest
and returns
the end-to-end delay bound. If a Map
instance is passed via the
parameter server_to_backlog_bound_map
, the map is filled with key-value-pairs
mapping servers (instances of Vertex
) to backlog bounds (instances
of Double
). If no such mapping is needed, pass null
instead.
flow_of_interest
- the flow for which the bounds shall be computedserver_to_backlog_bound_map
- a Map
instance that on return is filled with
<server,backlog bound>-pairs; pass null
if no such mapping is needed
public Curve performSeparatedFlowAnalysis(Flow flow_of_interest)
flow_of_interest
and returns
the end-to-end service curve.
flow_of_interest
- the flow for which the end-to-end service curve shall be computed
public Curve performPMOOAnalysis(Flow flow_of_interest)
flow_of_interest
and returns the end-to-end service curve.
flow_of_interest
- the flow for which the end-to-end service curve shall be computed
protected Curve getPMOOServiceCurve(java.util.List path, java.util.Set flows_of_interest)
flows_of_interest
.
This service curve is a concatenation of all servers on the given edge path
path
that have outgoing edges contained in the path (i.e. the
server at which the path ends is not included).computePMOOServiceCurve()
is invoked,
which does the real work of concatenating the service curves.computeOutputBound()
method that is also used for the total flow
and separated flow analyses or the new computePMOOOutputBound()
method that results in tighter bounds but also increases computation effort.
The latter recursively calls this method again. It is also possible to use
a mixture of both, using the PMOO output bound for the first levels of recursion
and the standard output bound for deeper levels. The recursion level from which
on the standard bound is used may be set via setMaxRecursionDepthForPMOO()
.
The default is to always use PMOO. To always use the standard output bound
computation set the maximum recursion depth to 0.setUseFlowProlongation()
.setUseArrivalCurveApproximation()
.
path
- the edge path along which service curves are concatenated (not including the
server at which the path ends)flows_of_interest
- the set of flows of interest
setMaxRecursionDepthForPMOO(int)
,
setUseFlowProlongation(boolean)
,
setUseArrivalCurveApproximation(boolean)
protected Curve computePMOOOutputBound(edu.uci.ics.jung.graph.Vertex server, java.util.Set flows_of_interest)
flows_of_interest
. The
difference to the standard output bound method is that this method tries to
compute tighter bounds by concatenating as many servers as possible using the
PMOO approach. It does so by searching from server
towards
the sinks of the flows contained in flows_of_interest
until it
reaches the server where all these flows first meet each other (the "splitting point").
It then concatenates all servers between the splitting point (inclusive) and
server
(exclusive).server
and not after the server as is the case with the standard
computateOutputBound().
server
- that all flows of interest flow intoflows_of_interest
- the set of flows of interest
protected edu.uci.ics.jung.graph.Vertex findSplittingPoint(edu.uci.ics.jung.graph.Vertex server, java.util.Set flows_of_interest)
flows_of_interest
first
all meet each other (when viewed from the source). When viewed from
server
towards the sink, this is the last server where all flows
are still together.
server
- flows_of_interest
-
protected void approximateArrivalCurves(java.util.Set all_interfering_flows, java.util.Map flow_bound_map)
setTokenBucketCountTarget()
(defaults to 2.0).
all_interfering_flows
- set of all flows interfering with the flow of interestflow_bound_map
- map of interfering flows to their arrival curveprotected void prolongFlows(java.util.List path, java.util.Set all_interfering_flows, java.util.List joining_flow_sets, java.util.Map flow_egress_map, java.util.Map flow_bound_map)
path
- all_interfering_flows
- joining_flow_sets
- flow_egress_map
- flow_bound_map
- protected boolean isFreeProlongation(Flow short_flow, Flow long_flow, java.util.List server_residual_rates, java.util.List passing_flow_sets, java.util.Map flow_min_residual_rates, java.util.Map flow_egress_map, java.util.Map flow_bound_map)
short_flow
- long_flow
- server_residual_rates
- passing_flow_sets
- flow_min_residual_rates
- flow_egress_map
- flow_bound_map
-
protected Curve computePMOOServiceCurve(java.util.List path, java.util.Set all_interfering_flows, java.util.List joining_flow_sets, java.util.Map flow_egress_map, java.util.Map flow_bound_map, int rec_depth)
path
according to
the PMOO approach and returns the result.computePartialPMOOServiceCurve()
for each combination. The
total PMOO service curve is the maximum of all partial service curves.
path
- edge path traversing the servers whose service curves shall be concatenated
(excluding the one at which the path ends).all_interfering_flows
- all flows that cross one of the servers on the path and
do not belong to the flows of interestjoining_flow_sets
- a list of sets with the flows that join at each serverflow_egress_map
- map of flows to egress points (integer index into the path)flow_bound_map
- map of flows to their arrival curvesrec_depth
- the current recursion level (optional)
protected Curve computePartialPMOOServiceCurve(Curve[] service_curves, java.util.Set all_interfering_flows, java.util.List joining_flow_sets, java.util.Map flow_egress_map, java.util.Map flow_bound_map, java.util.Map flow_tb_iter_map, int[] server_rl_iters)
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |