Package org.networkcalculus.dnc.network.server_graph

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

        public 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