Class ServerGraph


  • public class ServerGraph
    extends java.lang.Object
    Servers in a server graph object correspond to buffers that may be shared by different flows.

    That means the path of a flow is a sequence of buffers crossed by it and the analysis operating on a server graph handles Server objects as such.

    Please consider this when modeling a server graph for analysis. E.g., assuming output buffering in a simple wireless sensor network with one transceiver per node there is a 1:1-relation between network graph connecting wireless sensor nodes and servers in the DNC server graph.

    A flows path, however, is a sequence of crossed buffers. As a flow usually does not reach the output buffer of its sink, the path should not contain a turn to it. Otherwise the flow interference pattern of the server graph will be too pessimistic, yet, the results remain valid.

    In practice, on can model a sink explicitly by setting the server's service curve to be an infinite burst after without delay ( see ServiceCurve.createZeroDelayBurst() ).

    • Field Detail

      • servers

        private java.util.Set<Server> servers
      • turns

        private java.util.Set<Turn> turns
      • flows

        private java.util.Set<Flow> flows
      • map__server__in_turns

        private java.util.Map<Server,​java.util.Set<Turn>> map__server__in_turns
      • map__server__out_turns

        private java.util.Map<Server,​java.util.Set<Turn>> map__server__out_turns
      • map__server__flows

        private java.util.Map<Server,​java.util.Set<Flow>> map__server__flows
      • map__server__source_flows

        private java.util.Map<Server,​java.util.Set<Flow>> map__server__source_flows
      • map__turn__flows

        private java.util.Map<Turn,​java.util.Set<Flow>> map__turn__flows
      • server_default_name_prefix

        private java.lang.String server_default_name_prefix
      • server_id_counter

        private int server_id_counter
      • map__id__server

        private java.util.Map<java.lang.Integer,​Server> map__id__server
      • turn_default_name_prefix

        private java.lang.String turn_default_name_prefix
      • turn_id_counter

        private int turn_id_counter
      • flow_default_name_prefix

        private java.lang.String flow_default_name_prefix
      • flow_id_counter

        private int flow_id_counter
      • map__id__flow

        private java.util.Map<java.lang.Integer,​Flow> map__id__flow
    • Constructor Detail

      • ServerGraph

        public ServerGraph()
    • Method Detail

      • remove

        private void remove​(java.util.Set<Server> servers_to_remove,
                            java.util.Set<Turn> turns_to_remove,
                            java.util.Set<Flow> flows_to_remove)
      • addServer

        public Server addServer​(java.lang.String alias,
                                ServiceCurve service_curve)
      • addServer

        public Server addServer​(ServiceCurve service_curve,
                                MaxServiceCurve max_service_curve)
        By default the server's use_max_sc and use_max_sc_output_rate are enabled
        Parameters:
        service_curve - The server's service curve.
        max_service_curve - The server's maximum service curve.
        Returns:
        The added server.
      • addServer

        public Server addServer​(java.lang.String alias,
                                ServiceCurve service_curve,
                                MaxServiceCurve max_service_curve)
        By default the server's use_max_sc and use_max_sc_output_rate are enabled
        Parameters:
        alias - The server's user-defined alias.
        service_curve - The server's service curve.
        max_service_curve - The server's maximum service curve.
        Returns:
        The added server.
      • addServer

        public Server addServer​(java.lang.String alias,
                                ServiceCurve service_curve,
                                MaxServiceCurve max_service_curve,
                                boolean use_max_sc,
                                boolean use_max_sc_output_rate)
      • updateServerAdditionInternally

        private void updateServerAdditionInternally​(Server new_server)
      • removeServer

        public void removeServer​(Server s)
                          throws java.lang.Exception
        Throws:
        java.lang.Exception
      • getSourceFlows

        public java.util.Set<Flow> getSourceFlows​(Server source)
      • getServer

        public Server getServer​(int id)
                         throws java.lang.Exception
        Throws:
        java.lang.Exception
      • getServers

        public java.util.Set<Server> getServers()
      • numServers

        public int numServers()
      • getInOutServers

        public java.util.Set<Server> getInOutServers()
        Returns the subsets of all nodes of the directed graph g that are neither sources nor sinks, i.e. who have both (a) predecessor(s) and (a) successor(s) (in-degree > 0 and out-degree > 0).
        Returns:
        the set of server nodes
      • getSourceSet

        public java.util.Set<Server> getSourceSet()
        Returns the subsets of all nodes of the directed graph g that are sources, i.e. whose predecessor set is empty (in-degree == 0).
        Returns:
        the set of source nodes
      • getSinkSet

        public java.util.Set<Server> getSinkSet()
        Returns the subsets of all nodes of the directed graph g that are sinks, i.e. whose successor set is empty (out-degree == 0).
        Returns:
        the set of sink nodes
      • degree

        public int degree​(Server s)
      • inDegree

        public int inDegree​(Server s)
      • outDegree

        public int outDegree​(Server s)
      • getInTurns

        public java.util.Set<Turn> getInTurns​(Server s)
        Returns a new set consisting of references to the servers.
        Parameters:
        s - The server whose inturns are returned.
        Returns:
        The incoming turns of s.
      • getOutTurns

        public java.util.Set<Turn> getOutTurns​(Server s)
        Returns a new set consisting of references to the servers.
        Parameters:
        s - The server whose outturns are returned.
        Returns:
        The outgoing turns of s.
      • getIncidentTurns

        public java.util.Set<Turn> getIncidentTurns​(Server s)
        Returns a new set consisting of references to the turns.
        Parameters:
        s - The server whose inturns and outturns are returned.
        Returns:
        The incident turns.
      • getNeighbors

        public java.util.Set<Server> getNeighbors​(Server s)
        Returns a new set consisting of references to the servers.
        Parameters:
        s - The server whose inturn sources and outturn destinations are returned.
        Returns:
        The neighboring servers of s.
      • getPredecessors

        public java.util.Set<Server> getPredecessors​(Server s)
        Returns a new set consisting of references to the servers.
        Parameters:
        s - The server whose inturn sources are returned.
        Returns:
        The source servers of incoming turns of s
      • getSuccessors

        public java.util.Set<Server> getSuccessors​(Server s)
        Returns a new set consisting of references to the servers.
        Parameters:
        s - The server whose outturn destinations are returned.
        Returns:
        The sink servers of outgoing turns of s.
      • addTurn

        public Turn addTurn​(Server source,
                            Server destination)
                     throws java.lang.Exception
        Throws:
        java.lang.Exception
      • addTurn

        public Turn addTurn​(java.lang.String alias,
                            Server source,
                            Server destination)
                     throws java.lang.Exception
        Throws:
        java.lang.Exception
      • removeTurn

        public void removeTurn​(Turn t)
                        throws java.lang.Exception
        Throws:
        java.lang.Exception
      • getTurns

        public java.util.Set<Turn> getTurns()
      • numTurns

        public int numTurns()
      • findTurn

        public Turn findTurn​(Server src,
                             Server dest)
                      throws java.lang.Exception
        Parameters:
        src - The turn's source.
        dest - The turn's destination.
        Returns:
        The turn from src to dest.
        Throws:
        java.lang.Exception - No turn from src to snk found in this server graph.
      • addFlow

        public Flow addFlow​(ArrivalCurve arrival_curve,
                            java.util.List path)
                     throws java.lang.Exception
        Throws:
        java.lang.Exception
      • addFlow

        protected Flow addFlow​(ArrivalCurve arrival_curve,
                               Path path)
                        throws java.lang.Exception
        Throws:
        java.lang.Exception
      • addFlow

        public Flow addFlow​(ArrivalCurve arrival_curve,
                            Server source,
                            Server sink)
                     throws java.lang.Exception
        Creates a flow and adds it to the server graph.
        Parameters:
        arrival_curve - The flow's arrival curve.
        source - Source for shortest path routing.
        sink - Sink for shortest path routing.
        Returns:
        The flow created and added to the server graph.
        Throws:
        java.lang.Exception - Could not create a path from the given source/sink-pair.
      • addFlow

        public Flow addFlow​(java.lang.String alias,
                            ArrivalCurve arrival_curve,
                            Server source,
                            Server sink)
                     throws java.lang.Exception
        Creates a flow and adds it to the server graph.
        Parameters:
        alias - The flow's user defined-alias.
        arrival_curve - The flow's arrival curve.
        source - Source for shortest path routing.
        sink - Sink for shortest path routing.
        Returns:
        The flow created and added to the server graph.
        Throws:
        java.lang.Exception - Could not create a path from the given source/sink-pair.
      • addFlow

        public Flow addFlow​(java.lang.String alias,
                            ArrivalCurve arrival_curve,
                            java.util.List path)
                     throws java.lang.Exception
        Creates a flow and adds it to the server graph.
        Parameters:
        alias - The flow's user defined-alias.
        arrival_curve - The flow's arrival curve.
        path - The flows path as a list of servers or turns.
        Returns:
        The flow created and added to the server graph.
        Throws:
        java.lang.Exception - The given path is not entirely in the server graph.
      • addFlow

        public Flow addFlow​(ArrivalCurve arrival_curve,
                            Server single_hop)
                     throws java.lang.Exception
        Creates a flow and adds it to the server graph.
        Parameters:
        arrival_curve - The flow's arrival curve.
        single_hop - The single hop the flow takes in the server graph.
        Returns:
        The flow created and added to the server graph.
        Throws:
        java.lang.Exception - The given server is not in the server graph.
      • addFlow

        public Flow addFlow​(java.lang.String alias,
                            ArrivalCurve arrival_curve,
                            Server single_hop)
                     throws java.lang.Exception
        Creates a flow and adds it to the server graph.
        Parameters:
        alias - The flow's user defined-alias.
        arrival_curve - The flow's arrival curve.
        single_hop - The single hop the flow takes in the server graph.
        Returns:
        The flow created and added to the server graph.
        Throws:
        java.lang.Exception - The given server is not in the server graph.
      • addFlowToServerGraph

        private Flow addFlowToServerGraph​(java.lang.String alias,
                                          ArrivalCurve arrival_curve,
                                          Path path)
                                   throws java.lang.Exception
        Throws:
        java.lang.Exception
      • removeFlow

        public void removeFlow​(Flow f)
                        throws java.lang.Exception
        Removes a flow from the server graph.
        Parameters:
        f - The flow to be removed.
        Throws:
        java.lang.Exception - Flow to be removed is not in this server graph's list of flows.
      • getFlows

        public java.util.Set<Flow> getFlows()
      • numFlows

        public int numFlows()
      • getFlow

        public Flow getFlow​(int id)
                     throws java.lang.Exception
        Throws:
        java.lang.Exception
      • getFlows

        public java.util.Set<Flow> getFlows​(Turn t)
      • getFlows

        public java.util.Set<Flow> getFlows​(java.util.Set<Turn> turns)
      • getFlows

        public java.util.Set<Flow> getFlows​(Server s)
      • getFlows

        public java.util.Set<Flow> getFlows​(Path p)
                                     throws java.lang.Exception
        Throws:
        java.lang.Exception
      • getFlowsPerServer

        public java.util.Map<Server,​java.util.Set<Flow>> getFlowsPerServer​(Path p,
                                                                                 java.util.Set<Flow> excluded_flows)
                                                                          throws java.lang.Exception
        Do not confuse with getServerJoiningFlowsMap
        Parameters:
        p - The path to split up into its hops and analyze for flows.
        excluded_flows - Flows to omit in the sorting operation.
        Returns:
        Map from a server to the flows present at this servers.
        Throws:
        java.lang.Exception - Could not sort although there may be flows.
      • getFlowsPerSubPath

        public java.util.Map<Path,​java.util.Set<Flow>> getFlowsPerSubPath​(Path p)
                                                                         throws java.lang.Exception
        For every distinct sub-path of p this method returns the flows taking it entirely.
        Parameters:
        p - The path to split up and analyze for flows.
        Returns:
        Map from a path to the flows taking exactly this tandem of servers.
        Throws:
        java.lang.Exception - Could not sort although there may be flows.
      • groupFlowsPerSubPath

        public java.util.Map<Path,​java.util.Set<Flow>> groupFlowsPerSubPath​(Path p,
                                                                                  java.util.Set<Flow> flows_to_group)
                                                                           throws java.lang.Exception
        Throws:
        java.lang.Exception
      • groupFlowsPerSubPathInternal

        private java.util.Map<org.apache.commons.math3.util.Pair<Server,​Path>,​java.util.Set<Flow>> groupFlowsPerSubPathInternal​(Path p,
                                                                                                                                            java.util.Set<Flow> flows_to_group)
                                                                                                                                     throws java.lang.Exception
        Throws:
        java.lang.Exception
      • groupFlowsPerInturnSubPath

        public java.util.Map<org.apache.commons.math3.util.Pair<Turn,​Path>,​java.util.Set<Flow>> groupFlowsPerInturnSubPath​(Path p,
                                                                                                                                       java.util.Set<Flow> flows_to_group)
                                                                                                                                throws java.lang.Exception
        Parameters:
        p -
        flows_to_group -
        Returns:
        Throws:
        java.lang.Exception
      • getSourceFlowArrivalCurve

        public ArrivalCurve getSourceFlowArrivalCurve​(Server source)
        Returns an aggregate arrival curve for all flows originating in source.

        Returns a null curve if there are no source flows at source.

        Parameters:
        source - The source of all flows to be aggregated.
        Returns:
        An aggregate arrival curve.
      • getSourceFlowArrivalCurve

        public ArrivalCurve getSourceFlowArrivalCurve​(Server source,
                                                      java.util.Set<Flow> source_flows)
        Returns an aggregate arrival curve for all flows originating in source and contained in the set outgoing_flows.

        Returns a null curve if the intersection of those sets of curves is empty.

        Parameters:
        source - The source of all flows to be aggregated.
        source_flows - The set of all flows to be aggregated.
        Returns:
        An aggregate arrival curve.
      • createPath

        public Path createPath​(Server server)
                        throws java.lang.Exception
        Throws:
        java.lang.Exception
      • createPath

        public Path createPath​(Turn t)
                        throws java.lang.Exception
        Throws:
        java.lang.Exception
      • createPath

        public Path createPath​(java.util.List path)
                        throws java.lang.Exception
        Throws:
        java.lang.Exception
      • createPathFromServers

        private Path createPathFromServers​(java.util.List<Server> path_servers)
                                    throws java.lang.Exception
        Throws:
        java.lang.Exception
      • createPathFromTurns

        private Path createPathFromTurns​(java.util.List<Turn> path_turns)
                                  throws java.lang.Exception
        Throws:
        java.lang.Exception
      • createPath

        public Path createPath​(java.util.List<Server> path_servers,
                               java.util.List<Turn> path_turns)
                        throws java.lang.Exception
        Throws:
        java.lang.Exception
      • getServerJoiningFlowsMap

        public java.util.Map<Server,​java.util.Set<Flow>> getServerJoiningFlowsMap​(Path path)
                                                                                 throws java.lang.Exception
        Parameters:
        path - The tandem of servers to check for flows.
        flows_to_join - Flows not in the return set
        null will be handled as empty set of flows.
        Returns:
        The joining flows.
        Throws:
        java.lang.Exception - Could not derive the joining flows even if there are.
      • getServerLeavingFlowsMap

        public java.util.Map<Server,​java.util.Set<Flow>> getServerLeavingFlowsMap​(Path path)
                                                                                 throws java.lang.Exception
        Throws:
        java.lang.Exception
      • getShortestPath

        public Path getShortestPath​(Server src,
                                    Server snk)
                             throws java.lang.Exception
        Calculates the shortest path between src and snk according to Dijkstra's algorithm
        Parameters:
        src - The path's source.
        snk - The path's sink.
        Returns:
        Dijkstra shortest path from src to snk.
        Throws:
        java.lang.Exception - Could not find a shortest path for some reason.
      • findSplittingServer

        public Server findSplittingServer​(Server server_common_dest,
                                          java.util.Set<Flow> flows_of_interest)
                                   throws java.lang.Exception
        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_common_dest - The common destination, excluded as a potential splitting server.
        flows_of_interest - The flows whose common subpath before server_common_dest is computed.
        Returns:
        the splitting point server The common source.
        Throws:
        java.lang.Exception - No splitting point prior to the common destination found.
      • copy

        public ServerGraph copy()
                         throws java.lang.Exception
        Creates a deep copy of this server graph.
        Returns:
        The copy.
        Throws:
        java.lang.Exception - Signals problems while instantiating the copy.
      • saveAs

        public void saveAs​(java.lang.String output_path,
                           java.lang.String file_name)
                    throws java.lang.Exception
        Throws:
        java.lang.Exception
      • saveAs

        public void saveAs​(java.lang.String output_path,
                           java.lang.String file_name,
                           java.lang.String package_name)
                    throws java.lang.Exception
        Throws:
        java.lang.Exception
      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object