unikl.disco.nc
Class NetworkAnalyser

java.lang.Object
  extended by unikl.disco.nc.NetworkAnalyser

public class NetworkAnalyser
extends java.lang.Object

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.

Author:
Frank A. Zdarsky

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 or a null-curve if no service curve is defined for the 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

use_fifo_service

protected boolean use_fifo_service
Whether to use FIFO service instead of blind multiplexing


use_gamma

protected boolean use_gamma
Whether to use maximum service curves in output bound computation


use_extra_gamma

protected boolean use_extra_gamma
Whether to constrain the output bound further through convolution with the maximum service curve


max_rec_depth_for_pmoo

protected int max_rec_depth_for_pmoo
How many levels of recursion the tighter computePMOOOutputBound() is used rather than standard computeOutputBound().


use_arrival_curve_approximation

protected boolean use_arrival_curve_approximation
Whether to use arrival curve approximation


token_bucket_count_target

protected double token_bucket_count_target
The targeted number of TBs per flow when reducing complexity


use_flow_prolongation

protected boolean use_flow_prolongation
Whether to prolong flows to reduce complexity


server_graph

protected edu.uci.ics.jung.graph.DirectedGraph server_graph
The server model graph to analyse


rec_depth

protected int rec_depth
The current recursion level


flows

protected java.util.List flows
A list of all flows in the network

Constructor Detail

NetworkAnalyser

public NetworkAnalyser(edu.uci.ics.jung.graph.DirectedGraph server_graph)
Parameters:
server_graph - the (server) graph to analyse
Method Detail

useFifoService

public boolean useFifoService()

setUseFifoService

public void setUseFifoService(boolean use_fifo_service)

useGamma

public boolean useGamma()

setUseGamma

public void setUseGamma(boolean use_gamma)

useExtraGamma

public boolean useExtraGamma()

setUseExtraGamma

public void setUseExtraGamma(boolean use_extra_gamma)

getMaxRecursionDepthForPMOO

public int getMaxRecursionDepthForPMOO()

setMaxRecursionDepthForPMOO

public void setMaxRecursionDepthForPMOO(int max_rec_depth_for_pmoo)

useFlowProlongation

public boolean useFlowProlongation()

setUseFlowProlongation

public void setUseFlowProlongation(boolean use_flow_prolongation)

isUseArrivalCurveApproximation

public boolean isUseArrivalCurveApproximation()

setUseArrivalCurveApproximation

public void setUseArrivalCurveApproximation(boolean use_arrival_curve_approximation)

getTokenBucketCountTarget

public double getTokenBucketCountTarget()

setTokenBucketCountTarget

public void setTokenBucketCountTarget(double token_bucket_count_target)

getServiceCurve

public Curve getServiceCurve(edu.uci.ics.jung.graph.Vertex server)
Returns the (minimum) service curve of a given server or a null-curve if no service curve is defined for the server.

Parameters:
server -
Returns:
the service curve

setServiceCurve

public void setServiceCurve(edu.uci.ics.jung.graph.Vertex server,
                            Curve service_curve)
Sets the service curve for the specified server.

Parameters:
server - the server
service_curve - the service curve

setServiceCurve

public 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

Parameters:
servers - the set of servers whose service curve shall be set
prototype_service_curve - the prototype service curve

getMaxServiceCurve

public 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.

Parameters:
server -
Returns:
the maximum service curve

setMaxServiceCurve

public void setMaxServiceCurve(edu.uci.ics.jung.graph.Vertex server,
                               Curve max_service_curve)
Sets the maximum service curve for the specified server.

Parameters:
server - the server
max_service_curve - the service curve

setMaxServiceCurve

public 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

Parameters:
servers - the set of servers whose maximum service curve shall be set
prototype_max_service_curve - the prototype maximum service curve

autoAdjustServerRate

public 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.
More precisely, if the ratio between the sum of the sustained rates of all flows crossing the server and the server's minimum service rate is higher than 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.

Parameters:
server -
target_link_utilization - the maximum link utilization for the server

convolveServiceCurves

public Curve convolveServiceCurves(java.util.List path)
Returns the convolution of the service curves of all servers on the given edge path path.
All servers having outgoing edges contained in the given edge path (i.e. all but the server at which the path ends) are included.

Parameters:
path - an edge path
Returns:
the convolved curve

convolveMaxServiceCurves

public Curve convolveMaxServiceCurves(java.util.List path)
Returns the convolution of the maximum service curves of all servers on the given edge path path.
All servers having outgoing edges contained in the given edge path (i.e. all but the server at which the path ends) are included.

Parameters:
path - an edge path
Returns:
the convolved curve

addFlow

public void addFlow(Flow flow)
Adds a flow to the network analyser. The flow instance has to be fully initialized, including the flow's path.

Parameters:
flow - the flow to be added

removeFlow

public void removeFlow(Flow flow)
Removes a flow from the network analyser.

Parameters:
flow - the flow to be removed

getFlows

public java.util.List getFlows()
Returns all flows registered with the network analyser.

Returns:
a list of flows

getFlowSet

public java.util.Set getFlowSet(edu.uci.ics.jung.graph.DirectedEdge e)
Returns a set containing all flows traversing the given edge e.

Parameters:
e - the traversed edge
Returns:
a set of traversing flows

getIncomingFlows

public 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.

Parameters:
predecessor -
server -
Returns:
a set of incoming flows

getAllIncomingFlows

public 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.

Parameters:
server -
Returns:
a set of all incoming flows

getSourceFlow

public 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.

Parameters:
source - the source of all flows to be aggregated
outgoing_flows - the set of all flows to be aggregated
Returns:
an aggregate arrival curve

getPredecessor

public 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.

Parameters:
server - the receiving server
f - the incoming flow
Returns:
the predecessor

getMaxFlowLength

public int getMaxFlowLength(java.util.List flows)
Returns the length of the longest flow in the given list of flows.

Parameters:
flows - a list of flows
Returns:
the length of the longest flow

getMaxUtilizationForCharnyBound

public double getMaxUtilizationForCharnyBound()
Returns the maximum server utilization for which the Charny bound exist.
The Charny bound makes the following assumptions:
  • All fresh arrival curves have token bucket form.
  • All (minimum) service curves have rate latency form.
  • Within an aggregate, packets are served in a FIFO manner.
  • If maximum service curves exist they are of peak rate form.
  • Sources do not send with a higher rate than the maximum rate of any server in the network.


getCharnyDelayBound

public double getCharnyDelayBound()
Returns the Charny delay bound if it exists, otherwise returns Double.POSITIVE_INFINITY.

Returns:
the delay bound
See Also:
getMaxUtilizationForCharnyBound()

getCharnyBacklogBounds

public java.util.Map getCharnyBacklogBounds()
Computes the Charny backlog bound for each server. If the bound exists, returns a map containing the servers (Vertex instances) as keys and their corresponding backlog bound (Double instances) as values. If the bound does not exist, returns an empty map.

Returns:
a map from servers to backlog bounds
See Also:
getMaxUtilizationForCharnyBound()

getHighestServerUtilization

public double getHighestServerUtilization()
Returns the highest server utilization in the network. For the existence of the Charny bounds this utilization must be smaller than getMaxUtilizationForCharnyBound().

Returns:
the highest server utilization
See Also:
getMaxUtilizationForCharnyBound()

computeOutputBound

public 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.
It does so by first iterating over all incoming edges of the server, summing up the output bounds for all flows of interest (incoming flows contained also in outgoing_flows) and all cross flows (incoming flows not contained in outgoing_flows).
In a next step, the cross flows are factored out of the service curve to obtain the effective service curve. Per default, blind multiplexing is assumed. To use FIFO service instead you need to invoke setUseFIFOService(true) on the analyser instance before computing any bounds.
The output bound is then computed using arrival and service curves only. Invoke 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.

Parameters:
server - the server at which the output bound is computed
outgoing_flows - set of flows for which the output bound is computed
Returns:
a Curve instance containing the output bound
See Also:
setUseFifoService(boolean), setUseGamma(boolean), setUseExtraGamma(boolean)

performFairQueueingAnalysis

public 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.
This analysis assumes that flows passing a server are isolated from each other by a scheduler that guarantees each flow a fair (and equal) share of the link.

Parameters:
flow_of_interest - the flow for which the end-to-end service curve is computed
Returns:
the end-to-end service curve

performTotalFlowAnalysis

public 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. 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.
A total flow analysis iterates over the path of the flow of interest, summing up the additional delay incurred by each server it traverses. Note that this form of analysis is based on FIFO assumptions.

Parameters:
flow_of_interest - the flow for which the bounds shall be computed
server_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
Returns:
the end-to-end delay bound

performSeparatedFlowAnalysis

public Curve performSeparatedFlowAnalysis(Flow flow_of_interest)
Performs a separated flow analysis for the flow_of_interest and returns the end-to-end service curve.
This analysis first blends out the flow of interest and then computes for each server along this flow's path the effective service curve that results if all remaining flows crossing this server receive their maximum amount of service. Then all effective service curves are concatenated to receive the end-to-end service curve from the perspective of the flow of interest.

Parameters:
flow_of_interest - the flow for which the end-to-end service curve shall be computed
Returns:
the end-to-end service curve

performPMOOAnalysis

public 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.

Parameters:
flow_of_interest - the flow for which the end-to-end service curve shall be computed
Returns:
the PMOO end-to-end service curve

getPMOOServiceCurve

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. 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).
For performance reasons, the method first computes various mappings of servers to incoming and leaving flows. It then computes the output bounds of all incoming flows. If there are rejoining flows (flows that were there before, then left and now join again), these are substituted for fresh flows. Finally, computePMOOServiceCurve() is invoked, which does the real work of concatenating the service curves.
The output bounds are computed using either the standard 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.
Several techniques that significantly reduce the complexity of the service curve computation are employed:
  • Flow Aggregation: Flows having the same ingress and egress points are always replaced by a single flow whose bound is the aggregate bound of all contained flows.
  • Flow Prolongation: Flows having the same ingress but different egress points may be aggregated by extending the shorter flow to the egress point of the longer flow. This technique is only used if it comes for free, i.e. it does not impact the output bound. This is the case if the prolongation does not affect the location of the bottleneck server passed by any of the prolonged flows. To activate this technique, use setUseFlowProlongation().
  • Arrival Curve Approximation: Approximates the arrival curves of incoming flows by a different arrival curve with a lower number of linear segments. This does have an effect on the output bound, but does not necessarily affect the delay bound. To enable this technique, use setUseArrivalCurveApproximation().

Parameters:
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
Returns:
the concatenated PMOO service curve
See Also:
setMaxRecursionDepthForPMOO(int), setUseFlowProlongation(boolean), setUseArrivalCurveApproximation(boolean)

computePMOOOutputBound

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. 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).
Note: The previous sentence means that the output bound is for the flows before server and not after the server as is the case with the standard computateOutputBound().

Parameters:
server - that all flows of interest flow into
flows_of_interest - the set of flows of interest
Returns:
the PMOO output bound

findSplittingPoint

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). When viewed from server towards the sink, this is the last server where all flows are still together.

Parameters:
server -
flows_of_interest -
Returns:
the splitting point server

approximateArrivalCurves

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. It removes segments in the order of ascending heights of a segment's projection onto the y-axis. It tries to continue until the average number of token buckets that each arrival curve can be decomposed into has reached the value set by setTokenBucketCountTarget() (defaults to 2.0).

Parameters:
all_interfering_flows - set of all flows interfering with the flow of interest
flow_bound_map - map of interfering flows to their arrival curve

prolongFlows

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. Tests first, whether this prolongation comes for free (i.e. without effect on the output bounds). If so, the internal management information is updated accordingly.

Parameters:
path -
all_interfering_flows -
joining_flow_sets -
flow_egress_map -
flow_bound_map -

isFreeProlongation

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. This is the case if the prolongation does not change the bottleneck server which is the server with the lowest residual rate encountered by any of the flows on the subpath that the prolonged flow shares.

Parameters:
short_flow -
long_flow -
server_residual_rates -
passing_flow_sets -
flow_min_residual_rates -
flow_egress_map -
flow_bound_map -
Returns:
whether the prolongation is for free or not

computePMOOServiceCurve

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.
It first decomposes all arrival curves (service curves) into token buckets (rate latency curves), enumerates over all combinations of token buckets and rate latency curves, and calls computePartialPMOOServiceCurve() for each combination. The total PMOO service curve is the maximum of all partial service curves.

Parameters:
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 interest
joining_flow_sets - a list of sets with the flows that join at each server
flow_egress_map - map of flows to egress points (integer index into the path)
flow_bound_map - map of flows to their arrival curves
rec_depth - the current recursion level (optional)
Returns:
the PMOO service curve

computePartialPMOOServiceCurve

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. For each flow considers only one of its token bucket components (selected via the flow_tb_iter_map) and for each service curve considers only one rate latency curve (selected via the server_rl_iters).

Returns:
a partial PMOO service curve